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.
 A: 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}$. 
A: 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.
