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

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

Attempt:
Let p be a prime divisor of .
Then ≡ 0 (mod p)
=> ≡ 0 (mod p)
=> ≡ 1 (mod p)
Let = order of n mod p
=> |3
=> = 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]

Originally Posted by kingwinner

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

Attempt:
Let p be a prime divisor of .
Then ≡ 0 (mod p)
=> ≡ 0 (mod p)
=> ≡ 1 (mod p)
Let = order of n mod p
=> |3
=> = 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.

From your solution...

Originally Posted by NonCommAlg

then therefore

Can you explain why this part is true? Where did you get 2n+1? and why is it conrugent to -3 (mod p)?

Thanks!

Originally Posted by kingwinner

From your solution...



Can you explain why this part is true? Where did you get 2n+1? and why is it conrugent to -3 (mod p)?

Thanks!

we assumed that which means for some integer then and so thus which means

is a quadratic residue modulo and so