Suppose is not a primitive root mod , so that for some .
Note that .
Moreover, and since each of the terms in the sum is . Hence , hence , so the order of is strictly less than , contradicting the assumption.
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?