1
$\begingroup$

let $P(n) = n^4 + an^3 + bn^2 + cn$

$M(a,b,c)$ returns largest $m$ that divides $P(n)$ for all n

then let function $S(N)$ return the sum of all $M(a,b,c)$ for $1 \le a,b,c \le N$

I don't need anyone to solve this for me but just point me in the right direction. I am trying to understand a simpler way to calculate $S(N)$ so I don't have to actually process every single combination of a,b, and c but I am having trouble finding patterns to take advantage of on a broad scale.

So far I know from trying all sorts of values that M(a,b,c) tends to return values of form $2^i \times 3^j$ where $i,j\ge0$.

  • 1
    This question is directly related to [402th](http://projecteuler.net/problem=402) Project Euler problem2012-11-21

1 Answers 1

1

Definition The gcd of a polynomial $P$, $\gcd(P) := \gcd(P(1),P(2),P(3),\ldots)$.

Lemma $\gcd(P)|P(i)$. proof: immediate.

Notation The reduction of $n$ mod $m$ is written $[n]_m$.

Lemma $\gcd(P)|[P(i)]_{P(1)}$. proof: By division algorithm we have $P(i) = qP(1) + [P(i)]_{P(1)}$, since $\gcd(P)|P(i)$ and $\gcd(P)|qP(1)$ the result is immediate.

Algorithm to compute gcd(P):  m <- P(1) loop {  loop for i = 1 to m {    s <- p(i)%m    if(s != 0) {      break    }  }  if(s == 0) return m  else m = s } 

the loop terminates since s < m.