# Using induction to show that $(\mathbb{Z}/p^a\mathbb{Z})^{\times}$ is cyclic.

I need to show that the group $(\mathbb{Z}/p^a\mathbb{Z})^{\times}$ is cyclic for odd prime $p$ and for $a\in \mathbb{N}^+$. I have already shown that $(\mathbb{Z}/p\mathbb{Z})^{\times}$ has a generator $g$ and so is cyclic. I have also shown that either $g$ or $g+p$ is a generator for $(\mathbb{Z}/p^2\mathbb{Z})^{\times}$.

How can I proceed to show that $(\mathbb{Z}/p^a\mathbb{Z})^{\times}$ is also cyclic for higher powers?

For the life of me I can't get it.

-
This is a very long problem, especially if you want any amount of details for the steps. Please consider telling us the attempts you've made or perhaps even splitting the question up to help us help you. – EuYu Nov 9 '12 at 1:27
This is the question I'm asked. Its part of a long, multistep problem. So far, I've show (Z/p^a Z)* has order (p^(a-1))(p-1). And I've shown that if (1), than (2) in the question. – Chloe.H Nov 9 '12 at 1:30
So you've shown that $(\mathbb{Z}/p\mathbb{Z})^{\times}$ and $(\mathbb{Z}/p^2\mathbb{Z})^{\times}$ are cyclic already? – EuYu Nov 9 '12 at 1:32
Ya we did the first one in class. The second one should follow since I proved that if g is a generator of (Z/pZ)* than g or g + p is a generator of (Z/p^2 Z)*. Right? – Chloe.H Nov 9 '12 at 1:33
Yes. Next time you should include information like that in the question. The long list of requirements turn away a lot of people. Do you mind if I edit your question to make it more clear? – EuYu Nov 9 '12 at 1:37

Lemma: Let $p$ be an odd prime and let $x$ be coprime to $p$. If for some exponent $k$ we have $$x\equiv 1 \pmod{p^k},\ \ \ \ \ \ x^p \not\equiv 1 \pmod{p^{k+1}}$$ then we also have $$x^p\equiv 1 \pmod{p^{k+1}},\ \ \ \ \ \ x^p \not\equiv 1 \pmod{p^{k+2}}$$ Proof: Let us consider the binomial theorem. Since $x\equiv 1 \pmod{p^k}$, there is some $n\in\mathbb{Z}$ such that $x = 1 + np^k$. The second congruence then requires $n\nmid p$. Taking the expression to the $p$th power then gives us $$x^p=(1+np)^p = \sum_{i=0}^p\binom{p}{i}n^ip^{ki}$$ In the above expression, all terms with $i\ge 2$ are necessarily divisible by $p^{k+2}$, therefore only the first two terms survive the congruence $$x^p \equiv 1 + np^{k+1} \not\equiv 1 \pmod{p^{k+2}}$$ but clearly, the second term is divisible by $p^{k+1}$ so we have $$x^p \equiv 1 \pmod{p^{k+1}}$$ The result is as desired. $\square$
From your work with $(\mathbb{Z}/p^2\mathbb{Z})^{\times}$, you know that there is some $g$ such that $$g^{p-1} \equiv 1 \pmod p,\ \ \ \ \ \ g^{p-1} \not\equiv 1\pmod{p^2}$$ Now use the above lemma to inductively lift the congruence into $p^a$.