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

• Feb 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?
• Feb 27th 2011, 05:59 PM
Bruno J.
Suppose $\displaystyle a$ is not a primitive root mod $\displaystyle p$, so that $\displaystyle a^k=1 \mod p$ for some $\displaystyle k<p-1$.

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

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