1. ## primitive root

Show that if n has a primitive root and if the odd prime p divides n, then n is of the form p^j or 2p^j.

Could you please show me how to do this question? Thank you very much.

2. Originally Posted by Jenny20
Show that if n has a primitive root and if the odd prime p divides n, then n is of the form p^j or 2p^j.

Could you please show me how to do this question? Thank you very much.
Not necessarily.*)

It really is a long proof.
First done by Gauss (I think).
It is long because it is divided into cases.

*)The theorem says it is either 2,4 p^n, 2*p^n where p is odd prime.

3. Can somebody help me out, I was thinking about a similar attempt.

If $\displaystyle n$ has a primitive root that means $\displaystyle \mathbb{Z}_n$ under addition and multiplication will be a finite field.
Thus,
$\displaystyle |\mathbb{Z}_n|=n$
That means,
$\displaystyle n=p^m$
Because finite fields are power of primes.

Apparently, I missed something. I happen to know that I am wrong because it is a well known theorem that I heard of it before. Can someone spot an error?

EDIT: I spotted my error. I was assuming $\displaystyle \phi (n)=n-1$ which is only true when it is a prime. I will now see if I can answer this question elegantly via finite fields.