For p = 2q+1 odd prime, 2^q = 1 mod p iff p = +- 1 mod 8. True or false?

Favorite Answer

I don't know if this helps but I think it's got to do with Euler's Criterion

http://en.wikipedia.org/wiki/Euler's_criterion

we just need to prove that 2 = x^2 mod ( 8n +/- 1)

I'm stuck now.

EDIT: http://en.wikipedia.org/wiki/Quadratic_residue#Composite_modulus

EDIT2: 2^q = -1 mod p iff p = +- 3 mod 8...Show more

We have

[(p -1)/2]! • 2^[(p - 1)/2] = (p - 1)(p - 3) ••• 4 • 2.

On the other hand,

(p - 1)(p - 3) ••• 4 • 2

= [(p - 1) • 2] [(p - 3) • 4] ••• k
(k = (p - 1)/2 or (p + 1)/2)

= [(-1) • 2] [(-3) • 4] ••• k

= [(-1) • (-1)^2 • 2] [(-1)^3 • (-1)^4 • 3 • 4] ••• [(-1)^(p - 1)/2 • (p - 1)/2] (mod p)

= (-1)^(1 + 2 + 3 + ••• + (p - 1)/2) 1 • 2 • 3 ••• (p - 1)/2 (mod p)

= (-1)^[1/2{(p - 1)/2 • (p + 1)/2}] • [(p - 1)/2]! (mod p)

= (-1)^(p^2 - 1)/8 • [(p - 1)/2]! (mod p).

Thus

[(p - 1)/2]! • 2^(p - 1)/2 = (-1)^(p^2 - 1)/8 • [(p - 1)/2]! (mod p).

Since 1, 2, ..., (p - 1)/2 are all < p, [(p - 1)/2]! is relatively prime to p. So we can cancel the [(p - 1)/2]! in the congruence to get

2^(p - 1)/2 = (-1)^(p^2 - 1)/8 (mod p).

But (-1)^(p^2 - 1)/8 = 1 (mod p) if and only if p = ± 1 (mod 8), so

2^(p - 1)/2 = 1 (mod p)

if and only if p = ± 1 (mod 8)....Show more

p^5 - 2q^2 = a million p^5 - a million = 2q^2 p-a million divides p^5 -a million and consequently 2q^2 observe that p and q are unusual primes considering that p=2 implies q=sqrt(31/2) no longer in Z q=2 implies p=(9)^(a million/5) no longer in Z. Now p-a million equals a million,2,q,2q,q^2, or 2q^2 so as that p=2,3,q+a million,2q+a million,q^2+a million, or 2q^2+a million We already understand p can't be 2. p=3 implies q=eleven p=q+a million or p=q^2+a million are impossible considering that p and q are unusual primes If p=2q^2+a million then p^4+p^3+p^2+p+a million=a million so as that p(p+a million)(p^2+a million)=0 => p=0,-a million,i,-i impossible considering that p is fundamental. If p=2q+a million then (2q+a million)^5-2q^2=a million so as that 2q(16q^4+40q^3+40q^2+19q+5)=0 so q=0 (a contradiction) or the 2nd component is 0, yet Descartes rule of indicators implies the 2nd component has no beneficial authentic root. consequently p=3, q=eleven is the unique answer. (i'm nonetheless attempting to return up with the slick answer)...Show more