Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Along the same vein of another question I've posted is another question that merges group theory with number theory. I havn't taken a formal course on group theory, and is likely why I'm stumped at these questions posed from elementary number theory. The question goes as

Let $p$ be an odd prime and $g$ a generator of the group $(\mathbb{Z}/p \mathbb{Z})^*$. I need to show that either $g$ or $g+p$ is a generator of $(\mathbb{Z}/p^2 \mathbb{Z})^*$

I'm not sure where to begin. Just need a push in the right direction.


share|cite|improve this question
Hint: reducing mod $p$ you would have to be a generator too. – fretty Nov 5 '12 at 18:59
Show that if $g^{p-1} \equiv 1 \bmod p^2$ then $(g+p)^{p-1} \not\equiv 1 \bmod p^2$. – Derek Holt Nov 5 '12 at 20:02
Note that an element of $(\mathbb Z/p^2\mathbb Z)^*$ has order $p(p-1)$ (that is, it is a generator) if it has order $>p$. Note further that is order $\pmod {p^2}$ cannot be smaller than its order $\pmod p$. – martini Nov 5 '12 at 20:54
up vote 1 down vote accepted

If $g$ is not primitive mod $p^2$, the fact that $\mathrm{ord}(g)$ divides $p(p-1)$ and is a multiple of $p-1$ implies that $\mathrm{ord}(g)=p-1$ exactly. The same holds for $g+p$.

So if neither $g$ nor $g+p$ is primitive mod $p^2$, we must have $g^{p-1} \equiv 1 \mod p^2$ and $(g+p)^{p-1} \equiv 1 \mod p^2$. (In particular, $g^{p-1} \equiv (g+p)^{p-1} \mod p^2$.) Yet $$(g+p)^{p-1} \equiv g^{p-1} + \binom{p-1}{1}g^{p-2}p \equiv g^{p-1}-pg^{p-2}\mod p^2,$$ and if this is congruent to $g^{p-1}$ mod $p^2$ it follows that $pg^{p-2} \equiv 0 \mod p^2$. This forces $g \equiv 0 \mod p$ as $\mathbb{Z}/p\mathbb{Z}$ is an integral domain. This is a contradiction, and our result follows.

share|cite|improve this answer
sorry, I'm just re-reading this a couple days later and realized I don't quite understand the line "If g is not primitive mod p2, the fact that ord(g) divides p(p−1) *and is a multiple of p−1* implies that ord(g)=p−1 exactly. We know since <g> = (Z/pZ)* that |g| in (Z/pZ)* = (p-1). Is this what implies |g| in (Z/p^2 Z)* is a multiple of (p-1)? – user45793 Nov 8 '12 at 19:29
or is it that since |(Z/p^2 Z)*| = p(p-1) that implies there exists a generator of order p(p-1) and hence every element of (Z/p^2 Z)* has order p(p-1) as well. – user45793 Nov 8 '12 at 19:33
..but am I able to assume right away that (Z/p^2 Z)* is cyclic? – user45793 Nov 8 '12 at 19:35
Let $k$ be the order of $g$ mod $p^2$. Then $g^k \equiv 1 \mod p^2$, so in particular $g^k \equiv 1 \mod p$. But this implies that $k$ is a multiple of the order of $g$ in $\mathbb{Z}/p\mathbb{Z}$, which we know is $p-1$ (as $g$ is a generator mod $p$). In other words, $p-1$ divides $k$. – A Walker Nov 8 '12 at 19:51
More generally, let $\phi :G \to H$ be a group homomorphism. If $g^k =e_G$, then $\phi(g)^k = \phi(e_G)=e_H$, so $\mathrm{ord}(\phi(g))$ divides $\mathrm{ord}(g)$ (if both are finite). In our case, our map is projection $\pi: \mathbb{Z}/p^2 \mathbb{Z} \to \mathbb{Z}/p\mathbb{Z}$. – A Walker Nov 8 '12 at 19:54

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.