# Prove that all primitive roots modulo $p$ are congruent to $a^k$?

Assume $p$ is a prime and $a$ is some primitive root modulo $p$.

I have already shown that if gcd$(k, p-1)=1$ then $a^k$ is also a primitive root modulo $p$.

So what I'm wondering is how to extend this to prove that all primitive roots modulo $p$ are congruent to $a^k$ (for some $k$ such that gcd$(k, p-1)=1$)?

Since $a$ is a primitive root of $p$, any $x$ not divisible by $p$ is congruent to $a^k$ for some positive integer $k$. In particular, any candidate for primitive root must be of shape $a^k$ for some $k$.
we show that if $\gcd(k,p-1)\gt 1$, then $a^k$ is not a primitive root of $p$.
Let $d=\gcd(k,p-1)$, where $d\gt 1$. Let $k=k_1d$, Then $$(a^k)^{(p-1)/d}=a^{k_1(p-1)}=(a^{p-1})^{k_1}\equiv 1\pmod{p}$$ Thus $a^k$ has order $\le (p-1)/d$, and therefore cannot be a primitive root of $p$.