Prove that 3 is a primitive root of $7^k$ for all $k \ge 1$

so I am trying to find out how to prove that 3 is a primitive root of $7^k$ for all $k \ge 1$. I am trying to prove this via induction. Thanks.

Solution 1:

The solution depends on how much theory we have available. The standard theorem here is that if $a$ is a primitive root of $p^2$, where $p$ is prime, then $a$ is a primitive root of $p^k$ for any $k\ge 2$.

So we need only verify that $3$ is a primitive root of $7^2$. This is in principle a computation, but we can speed it up. It is easy to verify directly that $3$ is a primitive root of $7$. For $7^2$, we need to show that $3$ has order $\varphi(7^2)=42$ modulo $7^2$. The possible orders are multiples of $6$ that divide $42$. so we need only show that $3$ does not have order $6$ modulo $7^2$. Calculate. We have $3^6=729\equiv 43\pmod{49}$.

Solution 2:

Just for semi-completeness, a proof of Andre's claim.

First, use that the multiplicative group $\mathbb Z_{p^k}^\times$ is cyclic.

So the number of generators is $a_k=\phi(p-1)(p-1)p^{k-2}$ for $k\geq 2$.

So that means that if $a_{k+1}=pa_k$. But the only generators modulo $p^{k+1}$ are generators modulo $p^k$, and there are only $pa_k$ numbers, modulo $p^{k+1}$ which are congruent to generators modulo $p^{k}$. So that means all such elements must be generators.

So this follows if we know that $\mathbb Z_{p^k}^\times$ is cyclic.