# Proof of $(\mathbb{Z}/p^k \mathbb{Z})^\times\cong\mathbb{Z}/\phi(p^k) \mathbb{Z}$

While learning some material about primitive roots, I read some algebraic approach of the proof of the existence of primitive roots.

I read this wikipedia article, however, I got a little bit confused with this following statement (why it is cyclic?) :

For each odd prime $$p^k$$, the corresponding $$(\mathbb{Z}/p^k \mathbb{Z})^\times$$ is a cyclic group of order $$\phi(p^k)= p^k - p^{k-1}$$, which may further factor into cyclic groups of prime-power orders.

I tried to prove that the order of $$\bar 2$$ in this group is $$\phi(p^k)$$, but didn’t make any progress.

$$\overline{2}$$ is not even a generator of $$(\mathbb{Z}/p\mathbb{Z})^{\times}$$ for each odd prime $$p$$. In the case $$p=7$$, we have $$2^3=8\equiv 1\mod 7.$$ Therefore, the order of $$\overline{2}$$ in $$(\mathbb{Z}/7\mathbb{Z})^{\times}$$ is $$3$$, whereas $$|(\mathbb{Z}/7\mathbb{Z})^{\times}|=6$$.