# $\left(\mathbb{Z}/p\mathbb{Z},\times\right)\cong\left(\mathbb{Z}/\left(p-1\right)\mathbb{Z},+\right)$?

I want to show that the multiplicative group of integers mod $p$ is isomorphic to the additive group of integers mod $p-1$, where $p$ is prime.

Assume that I only know what you would find in a graduate, introductory abstract algebra text.

I exhaustively checked that $\left(\mathbb{Z}/7\mathbb{Z},\times\right)\cong\left(\mathbb{Z}/6\mathbb{Z},+\right)$. Unfortunately, the isomorphism is not better than a manual mapping from six elements to six elements; I could find no simple formula.

Moreover, I noticed that this group has one element of order $1$, one element of order $2$, two elements of order $3$, and two elements of order $6$. I am thus thinking that the converse of Lagrange's theorem holds for this class of groups, which I believe should help.

• Most intro abstract algebra texts should classify unit groups $(\Bbb Z/n\Bbb Z)^\times$ in full generality, in addition to proving finite multiplicative groups of units in fields are cyclic. (Also, quibble: $(\Bbb Z/p\Bbb Z,\times)$ is not a group since it includes $0$. The notation $R^\times$ is used for the group of units of a ring $R$.) I don't think there is a "truly easy" proof. Indeed, primitive elements mod $p$ are not characterized in any simple way - in practice we find them using algorithms! – anon Oct 30 '15 at 23:46

It's easier to answer this by first examining the behavior of $\Bbb Z/n\Bbb Z$ under multiplication. It turns out that $0$ isn't very interesting, so it's more enlightening to look at just the non-zero elements.

$\Bbb Z/6\Bbb Z$ is particularly interesting (and small). Here, we can observe a few things:

1.) $1$ is a multiplicative identity.

2.) $2,3$ and $4$ are zero-divisors:

$2\cdot 3 = 0$, and $3 \cdot 4 = 0$.

3.) $1$ and $5$ (which we can also think of as $-1$) have multiplicative inverses, they are units.

So why are some non-zero elements zero divisors, and others units? It turns out that this is because $\gcd(k,6) = 1$, only when $k = 1, 5$ (for $k \in \{1,2,3,4,5\}$). I urge you to explore this further (there are plenty of questions asked about it on this site). This proves to be true, in general; in fact, the group of units of $\Bbb Z/n\Bbb Z$ turns out to be (isomorphic to) the automorphism group of $\Bbb Z/n\Bbb Z$ (think about why this must be so: if $x \mapsto ax$ is a bijective map $\Bbb Z/n\Bbb Z \to \Bbb Z/n\Bbb Z$, doesn't $a$ need to be invertible?).

Well, if $n$ is prime, all of $k \in \{1,2,\dots,p-1\}$ will satisfy $\gcd(k,p) = 1$.

Since $\Bbb Z/n\Bbb Z$ already forms a commutative ring (with unity), this is enough to show that $\Bbb Z/p\Bbb Z$ forms a field, typically denoted $\Bbb F_p$ (the Galois field of order $p$). In any field $F$, there exists at most $n$ roots to a polynomial $f(x) \in F[x]$ of degree $n$ (you can use induction and the remainder theorem to prove this, it's again a worth-while exercise).

Now, by Lagrange, we have that every element $a$ of $\Bbb Z/p\Bbb Z - \{0\}$ satisfies $a^{p-1} = 1$, that is, we have $p-1$ distinct roots of $x^{p-1} - 1 \in \Bbb Z/p \Bbb Z[x]$, which is all of them (this often goes by the name "Fermat's Little Theorem").

Now if $d$ is any divisor of $p-1$, we have that $x^d - 1$ is a divisor of $x^{p-1} - 1$ (try this with $p = 13$ and $d = 3$). It follows that for any such divisor $d$, we have at most $d$ elements of (multiplicative) order $d$ in $\Bbb F_p$ (since there are at most $d$ roots to $x^d - 1$ in $\Bbb F_p$).

If we group our (non-zero) elements by order, say $n_d$ is the number of elements of order $d$, we find that:

$|\Bbb F_p^{\ast}| = \sum\limits_{d|(p-1)} n_d \leq \sum\limits_{d|(p-1)} d = |\Bbb F_p^{\ast}|$

It follows from this that our two inner sums must be equal, that is, we have exactly $d$ elements with order dividing $d$.

Thus $((\Bbb Z/p\Bbb Z)^{\ast}, \times)$ is a group such that it has exactly one subgroup of order $d$ (namely the elements whose multiplicative orders divide $d$) for every divisor of $p-1$. Such a group must be cyclic (this is because we have the identity:

$\sum\limits_{d|n} \varphi(d) = n$, where $\varphi(d)$ is the Euler totient function. For example, the divisors of $12$ are $1,2,3,4,6$ and $12$, and $\varphi(1) = 1, \varphi(2) = 1,\varphi(3) = 2,\varphi(4) = 2, \varphi(6) = 2$ and $\varphi(12) = 4$, and indeed, $12 = 1 + 1 + 2 + 2 + 2 + 4$ -this identity is another worth-while topic for you to investigate. Note that not only does this tell us $\Bbb F_p^{\ast}$ has a generator, it tells us we have $\varphi(p-1)$ such generators).

Unfortunately, this does not explicitly display the desired isomorphism:

$((\Bbb Z/p\Bbb Z)^{\ast},\times) \to (\Bbb Z/(p-1)\Bbb Z, +)$

it only shows it exists. The actual isomorphism is equivalent to what is called in computer science a "discrete log table" (it is a finitary version of the familiar logarithms from analysis), and unfortunately, the best approach for finding a generator to serve as a "base" is trial-and error.

The desired isomorphism is not, unfortunately, obtained just by "subtracting one", for example, with $p = 5$, one possible isomorphism is:

$[1]_5 \mapsto [0]_4 \\ [2]_5 \mapsto [1]_4 \\ [3]_5 \mapsto [3]_4 \\ [4]_5 \mapsto [2]_4.$

It was mentioned in the comments above that $\mathbb{Z} / p\mathbb{Z}$ is not a group under multiplication because $0$ does not have an inverse. Now, every other element does have an inverse. So let $G = \mathbb{Z} / p\mathbb{Z} - \{0\}$. You can show that this is a group under multiplication. In fact, you can show that this is cyclic. If you know this and you know that $\mathbb{Z} / (p-1)\mathbb{Z}$ is cyclic of order $p-1$, then you know they are isomorphic because there is (up to isomorphism) only one cyclic group of order $n$ for each natural number $n$.

The only thing about the above that requires a bit of work is showing that $G$ is cyclic.

• This made perfect sense. What would be required to show that $(\mathbb Z/p\mathbb Z)^\times$ is cyclic? – wjm Oct 31 '15 at 0:05
• In $\mathbb{Z} / p\mathbb{Z}$, every non-zero element is invertible. Thus $(\mathbb{Z} / p\mathbb{Z})^{\times}$ is a finite group of order $p-1$. Now you can use the fact that every abelian finite group $G$ has an element of order the exponant $e$ of $G$, defined as the least common multiple of the orders of the elements of $G$. Finally the conclusion comes easily by studying the polynomial $X^{e} -1$ lying in $\mathbb{Z} / p\mathbb{Z}[X]$. @Josué – krirkrirk Oct 31 '15 at 0:11