# Thread: Prime divisors of n^2 + n + 1

1. ## Prime divisors of n^2 + n + 1

Prove that for ANY integer n, $n^2+n+1$ has no prime divisors of the form 6m-1.
==========================================

Attempt:
Let p be a prime divisor of $n^2+n+1$.
Then $n^2+n+1$ 0 (mod p)
=> $n^3 -1 = (n-1)(n^2+n+1)$ 0 (mod p)
=> $n^3$ ≡ 1 (mod p)
Let $e_p(n)$ = order of n mod p
=> $e_p(n)$|3
=> $e_p(n)$= 1 or 3

Now I'm stuck here. How to finish the proof from here?

Any help is greatly appreciated!

[also under discussion in math links forum]

2. Originally Posted by kingwinner
Prove that for ANY integer n, $n^2+n+1$ has no prime divisors of the form 6m-1.
==========================================

Attempt:
Let p be a prime divisor of $n^2+n+1$.
Then $n^2+n+1$ 0 (mod p)
=> $n^3 -1 = (n-1)(n^2+n+1)$ 0 (mod p)
=> $n^3$ ≡ 1 (mod p)
Let $e_p(n)$ = order of n mod p
=> $e_p(n)$|3
=> $e_p(n)$= 1 or 3

Now I'm stuck here. How to finish the proof from here?

Any help is greatly appreciated!

[also under discussion in math links forum]
see here for two solutions.

Originally Posted by NonCommAlg
then $(2n+1)^2 \equiv -3 \mod p.$ therefore $\left (\frac{-3}{p} \right) = 1$
Can you explain why this part is true? Where did you get 2n+1? and why is it conrugent to -3 (mod p)?

Thanks!

4. Originally Posted by kingwinner
we assumed that $p \mid n^2+n+1,$ which means $n^2+n+1=kp,$ for some integer $k.$ then $4n^2+4n+4=4kp$ and so $(2n+1)^2+3=4kp.$ thus $(2n+1)^2 \equiv -3 \mod p,$ which means $-3$
is a quadratic residue modulo $p$ and so $\left (\frac{-3}{p} \right)=1.$