2
$\begingroup$

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.

$\endgroup$
  • 4
    $\begingroup$ 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! $\endgroup$ – anon Oct 30 '15 at 23:46
1
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ This made perfect sense. What would be required to show that $(\mathbb Z/p\mathbb Z)^\times$ is cyclic? $\endgroup$ – wjm Oct 31 '15 at 0:05
  • 2
    $\begingroup$ 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é $\endgroup$ – krirkrirk Oct 31 '15 at 0:11

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.