Let p = 2^(k) + 1 be a prime. Prove that if a is a natural number and a is a quadratic non-residue modulo p, then a is a primitive root modulo p.

thanks :)

Printable View

- Apr 25th 2010, 11:11 AMTandPrimitive Root proof
Let p = 2^(k) + 1 be a prime. Prove that if a is a natural number and a is a quadratic non-residue modulo p, then a is a primitive root modulo p.

thanks :) - Apr 25th 2010, 11:32 AMchiph588@
Euler's Criterion says $\displaystyle -1 = \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \bmod{p} $

But $\displaystyle \frac{p-1}{2} = 2^{k-1} $, so we know $\displaystyle a^{2^{k-1}}\equiv -1 \bmod{p} $.

Now all the divisors of $\displaystyle \phi(p) $ are of the form $\displaystyle 2^b $ where $\displaystyle b\leq k $. So suppose there exists $\displaystyle b < k-1 $ such that $\displaystyle a^{2^b}\equiv 1\bmod{p} $. This would however imply $\displaystyle a^{2^{k-1}}\equiv 1 \bmod{p} $ since $\displaystyle 2^b\mid2^{k-1} $, which is a contradiction.

Thus we see for every proper divisor $\displaystyle b $ of $\displaystyle \phi(p) $, $\displaystyle a^b\not\equiv 1 \bmod{p}\implies a $ is a primitive root modulo $\displaystyle p $.