I really need to answer this question quickly for my homework due tomorrow:
Let $a,p \in \Bbb N$, $p$ is prime, $a$ is a primitive root modulo $p$ that $p^2\nmid (a^{p-1}-1)$.
Prove that $a$ is primitive root modulo $p^2$.
My thoughts: I proved that $a^{\phi (p^2)} = a^{{(p-1)}^p} \equiv 1\ mod\ p^2$ but I don't know how to continue from here.
Thank you for helping
Best Answer
Denote $$n:=ord_a(p^2)$$ which is the smallest positive integer $\ n\ $ satisfying $$a^n\equiv 1\mod p^2$$
Since $\ \varphi(p^2)=p(p-1)\ $ , we know $\ n\mid p(p-1)\ $
We also know $\ n\nmid p-1\ $ otherwise we would have $\ a^{p-1}\equiv 1\mod p^2\ $
So, $\ n\ $ must be a multiple of $\ p\ $. Assume $\ n=kp\ $ with $\ k<p-1\ $
Then, we would have $\ a^{pk}=(a^p)^k\equiv a^k\equiv 1\mod p\ $ , but this is impossible since $\ a\ $ is a primitive root mod $\ p\ $. Hence, we must have $\ n=p(p-1)\ $