Primitive Root proof

**Tand** · April 25th 2010, 11:11 AM

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

**chiph588@** · April 25th 2010, 11:32 AM

Originally Posted by Tand

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

Euler's Criterion says $-1 = \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \bmod{p}$

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

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

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

Thread: Primitive Root proof

LinkBack

Thread Tools

Display

Primitive Root proof

Similar Math Help Forum Discussions

Prove if a is a primitive root mod p^2, then it is a primitive root mod p

Primitive root of 2^n + 1

primitive root

primitive root

Primitive root

Search Tags