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

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

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

Attempt:
Let p be a prime divisor of $\displaystyle n^2+n+1$.
Then $\displaystyle n^2+n+1$ 0 (mod p)
=> $\displaystyle n^3 -1 = (n-1)(n^2+n+1)$ 0 (mod p)
=> $\displaystyle n^3$ ≡ 1 (mod p)
Let $\displaystyle e_p(n)$ = order of n mod p
=> $\displaystyle e_p(n)$|3
=> $\displaystyle 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, $\displaystyle n^2+n+1$ has no prime divisors of the form 6m-1.
==========================================

Attempt:
Let p be a prime divisor of $\displaystyle n^2+n+1$.
Then $\displaystyle n^2+n+1$ 0 (mod p)
=> $\displaystyle n^3 -1 = (n-1)(n^2+n+1)$ 0 (mod p)
=> $\displaystyle n^3$ ≡ 1 (mod p)
Let $\displaystyle e_p(n)$ = order of n mod p
=> $\displaystyle e_p(n)$|3
=> $\displaystyle 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 $\displaystyle (2n+1)^2 \equiv -3 \mod p.$ therefore $\displaystyle \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 $\displaystyle p \mid n^2+n+1,$ which means $\displaystyle n^2+n+1=kp,$ for some integer $\displaystyle k.$ then $\displaystyle 4n^2+4n+4=4kp$ and so $\displaystyle (2n+1)^2+3=4kp.$ thus $\displaystyle (2n+1)^2 \equiv -3 \mod p,$ which means $\displaystyle -3$
is a quadratic residue modulo $\displaystyle p$ and so $\displaystyle \left (\frac{-3}{p} \right)=1.$