My assignment asks me to prove $\left(\mathbb{Z}/p^{d} \mathbb{Z}\right)^{\times}$ is cyclic for prime $p>2$ and for any positive integer $d$.
They propose proving this by induction.
The base case:
I set $d=1$, then Fermat's Little Theorem states that:
$$\exists \hspace{3pt} x \in \left(\mathbb{Z}/p^{} \mathbb{Z}\right)^{\times} \hspace{7pt} s.t \hspace{6pt} x^{p-1} \equiv 1 \pmod p $$
Therefore, the statement is true for $d=1$. I am confused with how to move forward from here. I know that I need to show: assuming the statement is true for some $d$, this then implies that it is true for $d+1$.
I tried to prove directly: $\exists x$ such that
$$x^{p-1} \equiv 1 \pmod {p^d} $$
$$\Rightarrow x^{p-1} - kp^{d} = 1 \hspace{17pt} k \in \mathbb{Z}$$
Multiplying by $p$, I get: $$\Rightarrow px^{p-1} - kp^{d+1} = p \hspace{17pt} k \in \mathbb{Z}$$
However, it seems that this strategy brings me nowhere. Does anyone know of any other approaches to this that are hopefully simpler?
I thought about using Chinese Remainder Theorem with the $p$ and $p^{d}$ case, which would imply the $p^{d+1}$ case, but this only works when $p$ and $p^d$ are coprime, right? (which is clearly never the case).
Any strategies, approaches, insight or advice would be greatly appreciated. Thanks!
A sketch:
As mentioned in @reuns' comment, you first prove that
$$(1+p)^{p^k}\equiv 1+p^{k+1}\mod p^{k+2}$$ by induction on $k$ (you'll need the multinomial formula for that). this proves that in $(\mathbf Z/p^d\mathbf Z)^\times$, the class of $1+p$ has order $p^{d-1}$.
On the other hand, in the cyclic group $(\mathbf Z/p\mathbf Z)^\times$, there exists an integer $n\bmod p$ with order $p-1$ , hence the order of $n\bmod p^d\:$ is a multiple of $p-1$, so that some power $n^r\bmod p^d$ has order exactly $p-1$. As $p-1$ and $p^{d-1}$ are coprime, $n^r(1+p)\bmod p^d$ has order $(p-1)p^{d-1}=\varphi(p^d)$.