# Generator of a Quotient Group

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.

Thanks!

-
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

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.

-
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