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!

  • 2
    $\begingroup$ Any $\mathbf Z/n\mathbf Z$ is cyclic, and you don't need to call lil' Fermat to see this. $\endgroup$ – Bernard Feb 4 at 22:14
  • 2
    $\begingroup$ 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$. $\endgroup$ – reuns Feb 4 at 22:29
  • 1
    $\begingroup$ 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 $\endgroup$ – Max Feb 4 at 22:41
  • 1
    $\begingroup$ $p$ is odd though $\endgroup$ – Mike Feb 4 at 22:43
  • 1
    $\begingroup$ 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.) $\endgroup$ – 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)$.

  • $\begingroup$ 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. $\endgroup$ – KCd Feb 4 at 23:16
  • $\begingroup$ 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$. $\endgroup$ – Bernard Feb 4 at 23:22
  • $\begingroup$ I agree. The edit looks good. $\endgroup$ – KCd Feb 4 at 23:35
  • $\begingroup$ 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$> $\endgroup$ – Mike Feb 5 at 2:25
  • $\begingroup$ 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. $\endgroup$ – Bernard Feb 5 at 10:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.