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

• February 27th 2011, 05:30 PM
uberbandgeek6
Prove if a is a primitive root mod p^2, then it is a primitive root mod p
Prove that if a is a primitive root mod p^2, then it is a primitive root mod p.

I have no idea where to go with this. I know that if a is a primitive root mod p^2 then: ord(mod p^2) a = phi(p^2) = p(p - 1), and a^(p(p-1)) = 1 mod p^2.

Where do I go from here?
• February 27th 2011, 05:59 PM
Bruno J.
Suppose $a$ is not a primitive root mod $p$, so that $a^k=1 \mod p$ for some $k.

Note that $a^{kp}-1 = (a^k-1)(a^{k(p-1)}+a^{k(p-2)}+\dots+1)$.

Moreover, $p \mid a^k-1$ and $p\mid a^{k(p-1)}+a^{k(p-2)}+\dots+1$ since each of the $p$ terms in the sum is $=1\mod p$. Hence $p^2 \mid (a^k-1)(a^{k(p-1)}+a^{k(p-2)}+\dots+1)$, hence $a^{kp}\equiv 1 \mod p^2$, so the order of $a$ is strictly less than $p(p-1)$, contradicting the assumption.