Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$.

share|improve this question
1  
This question is directly related to 402th Project Euler problem –  sindikat Nov 21 '12 at 14:03

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.