# Proving $\left(\mathbb{Z}/p^{d} \mathbb{Z}\right)^{\times}$ is cyclic for prime p

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!

• Any $\mathbf Z/n\mathbf Z$ is cyclic, and you don't need to call lil' Fermat to see this. – Bernard Feb 4 at 22:14
• The first step is to say for $p$ odd prime : $(1+p)^{p^k} = \sum_{j=0}^{p^k} {p^k \choose j} p^{p^k-j} \equiv 1+p^{k+1} \bmod p^{k+2}$, from which you find the subgroup of $\mathbb{Z}/p^d \mathbb{Z}^\times$ generated by $1+p$. Then look at the surjective morphism $\mathbb{Z}/p^d \mathbb{Z}^\times \to \mathbb{Z}/p \mathbb{Z}^\times$ (what is its kernel ?) to see $\mathbb{Z}/p^d \mathbb{Z}^\times$ has an element of order $p-1$. – reuns Feb 4 at 22:29
• Your proof for $d=1$ isn't correct: in $(\mathbb{Z/2Z})^2$, every $x$ satisfies $4x = 0$ in particular there exists one that does; but it's not cyclic for that matter – Max Feb 4 at 22:41
• $p$ is odd though – Mike Feb 4 at 22:43
• The Chinese remainder theorem is about relatively prime moduli. Therefore it is not realistic to think it will help you combine an argument mod $p$ and $p^d$ in a direct way to say something about modulus $p^{d+1}$. (Of course $p-1$ and $p^{d-1}$ are relatively prime, so maybe CRT is useful when working with those moduli.) – KCd Feb 4 at 23:21

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)$$.

• Your notation is sloppy. Don't say "$n$ has order $p-1 \bmod p$" since it looks like you are writing about the order reduced modulo $p$. Instead say "$n \bmod p$ has order $p-1$." Fix the same kind of awkward writing when discussing orders of integers modulo $p^d$. Also, I feel the reasoning you give to get a unit mod $p^d$ with order $p-1$ needs more work: when $n \bmod p$ has order $p-1$, why should some power $n^r \bmod p^d$ have order $p-1$? Of course it might be okay to leave this for the OP to think about, but there is definitely something more needed there for a full argument. – KCd Feb 4 at 23:16
• I recall it's only a sketch, not a detailed solution. Roughly speaking, theorder $p-1$ is the generator of the subgroup of periods, so the order $\bmod p^d$ is a multiple of $p-1$, namely it is $r(p-1)$ for some $r$, in which case $n^r\bmod p^d$ has order $p-1$. – Bernard Feb 4 at 23:22
• I agree. The edit looks good. – KCd Feb 4 at 23:35
• Wait, why does the fact that the ord$(n^r)$ $=p-1$ coprime to ord$(1+p) =p^{d-1}$ imply that the order of $n^r(1+p)$ is the product? Couldn't there be some $\ell$ of the form $\ell = (p-1)p^r; r<d-1$ such that $(n^r(1+p))^{\ell} \equiv 1$ $\mod p^d$> – Mike Feb 5 at 2:25
• This results from the Chinese remainder theorem and the structure theorem for finite abelian groups* $1+p$ and $n^p$ are not in the same component of $\mathbf Z/p^d\mathbf Z$, hence the order of he product is the l.c.m. of the h, i.e. their product. – Bernard Feb 5 at 10:34