Modulo Multiplication Group

A Finite Group $M_m$ of Residue Classes prime to $m$ under multiplication mod $m$. $M_m$ is Abelian of Order $\phi(m)$, where $\phi(m)$ is the Totient Function. The following table gives the modulo multiplication groups of small orders.

$M_m$	Group	$\phi(m)$	Elements
$M_2$	$\left\langle{e}\right\rangle{}$	1	1
$M_3$	$Z_2$	2	1, 2
$M_4$	$Z_2$	2	1, 3
$M_5$	$Z_4$	4	1, 2, 3, 4
$M_6$	$Z_2$	2	1, 5
$M_7$	$Z_6$	6	1, 2, 3, 4, 5, 6
$M_8$	$Z_2\otimes Z_2$	4	1, 3, 5, 7
$M_9$	$Z_6$	6	1, 2, 4, 5, 7, 8
$M_{10}$	$Z_4$	4	1, 3, 7, 9
$M_{11}$	$Z_{10}$	10	1, 2, 3, 4, 5, 6, 7, 8, 9, 10
$M_{12}$	$Z_2\otimes Z_2$	4	1, 5, 7, 11
$M_{13}$	$Z_{12}$	12	1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
$M_{14}$	$Z_6$	6	1, 3, 5, 9, 11, 13
$M_{15}$	$Z_2\otimes Z_4$	8	1, 2, 4, 7, 8, 11, 13, 14
$M_{16}$	$Z_2\otimes Z_4$	8	1, 3, 5, 7, 9, 11, 13, 15
$M_{17}$	$Z_{16}$	16	1, 2, 3, ..., 16
$M_{18}$	$Z_6$	6	1, 5, 7, 11, 13, 17
$M_{19}$	$Z_{18}$	18	1, 2, 3, ..., 18
$M_{20}$	$Z_2\otimes Z_4$	8	1, 3, 7, 9, 11, 13, 17, 19
$M_{21}$	$Z_2\otimes Z_6$	12	1, 2, 4, 5, 7, 8, 10, 11, 13, 16, 17, 19
$M_{22}$	$Z_{10}$	10	1, 3, 5, 7, 9, 13, 15, 17, 19, 21
$M_{23}$	$Z_{22}$	22	1, 2, 3, ..., 22
$M_{24}$	$Z_2\otimes Z_2\otimes Z_2$	8	1, 5, 7, 11, 13, 17, 19, 23

$M_m$ is a Cyclic Group (which occurs exactly when $m$ has a Primitive Root) Iff $m$ is of one of the forms $m=2$, 4, $p^n$, or $2p^n$, where $p$ is an Odd Prime and $n\geq 1$ (Shanks 1993, p. 92).

Isomorphic modulo multiplication groups can be determined using a particular type of factorization of $\phi(m)$ as described by Shanks (1993, pp. 92-93). To perform this factorization (denoted $\phi_m$), factor $m$ in the standard form

$$m={p_1}^{a_1}{p_2}^{a_2}\cdots {p_n}^{a_n}.$$ (1)

Now write the factorization of the Totient Function involving each power of an Odd Prime

$$\phi({p_i}^{a_i})=(p_i-1){p_i}^{a_i-1}$$ (2)

as

$$\phi({p_i}^{a_i})=\left\langle{{q_1}^{b_1}}\right\rangle{}\l... ..._s}}\right\rangle{}\left\langle{{p_i}^{a_i-1}}\right\rangle{},$$ (3)

where

$$p_i-1={q_1}^{b_1}{q_2}^{b_2}\cdots{q_s}^{b_s},$$ (4)

$\left\langle{q^b}\right\rangle{}$ denotes the explicit expansion of $q^b$ (i.e., $5^2=25$), and the last term is omitted if $a_i=1$. If $p_1=2$, write

$$\phi(2^{a_1})=\cases{ 2 & for $a_1=2$\cr 2\left\langle{2^{a_1-2}}\right\rangle{} & for $a_1>2$.\cr}$$ (5)

Now combine terms from the odd and even primes. For example, consider $m=104=2^3\cdot 13$. The only odd prime factor is 13, so factoring gives $13-1=12=\left\langle{2^2}\right\rangle{}\left\langle{3}\right\rangle{}=3\cdot 4$. The rule for the powers of 2 gives $2^3=2\left\langle{2^{3-2}}\right\rangle{}=2\left\langle{2}\right\rangle{}=2\cdot 2$. Combining these two gives $\phi_{104}=2\cdot 2\cdot 3\cdot 4$. Other explicit values of $\phi_m$ are given below.

$$\phi_3 = 2$$

$$\phi_4 = 2$$

$$\phi_5 = 4$$

$$\phi_6 = 2$$

$$\phi_{15} = 2\cdot 4$$

$$\phi_{16} = 2\cdot 4$$

$$\phi_{17} = 16$$

$$\phi_{104} = 2\cdot 2\cdot 3\cdot 4$$

$$\phi_{105} = 2\cdot 2\cdot 3\cdot 4.$$

$M_m$ and $M_n$ are isomorphic Iff $\phi_m$ and $\phi_n$ are identical. More specifically, the abstract Group corresponding to a given $M_m$ can be determined explicitly in terms of a Direct Product of Cyclic Groups of the so-called Characteristic Factors, whose product is denoted $\Phi_n$. This representation is obtained from $\phi_m$ as the set of products of largest powers of each factor of $\phi_m$. For example, for $\phi_{104}$, the largest power of $2$ is $4=2^2$ and the largest power of 3 is $3=3^1$, so the first characteristic factor is $4\times 3=12$, leaving $2\cdot 2$ (i.e., only powers of two). The largest power remaining is $2=2^1$, so the second Characteristic Factor is 2, leaving 2, which is the third and last Characteristic Factor. Therefore, $\Phi_{104}=2\cdot 2\cdot 4$, and the group $M_m$ is isomorphic to $Z_2\otimes Z_2\otimes Z_4$.

The following table summarizes the isomorphic modulo multiplication groups $M_n$ for the first few $n$ and identifies the corresponding abstract Group. No $M_m$ is Isomorphic to $Z_8$, $Q_8$, or $D_4$. However, every finite Abelian Group is isomorphic to a Subgroup of $M_m$ for infinitely many different values of $m$ (Shanks 1993, p. 96). Cycle Graphs corresponding to $M_n$ for small $n$ are illustrated above, and more complicated Cycle Graphs are illustrated by Shanks (1993, pp. 87-92).

Group	Isomorphic $M_m$
$\left\langle{e}\right\rangle{}$	$M_2$
$Z_2$	$M_3$, $M_4$, $M_6$
$Z_4$	$M_5$, $M_{10}$
$Z_2\otimes Z_2$	$M_8$, $M_{12}$
$Z_6$	$M_7$, $M_9$, $M_{14}$, $M_{18}$
$Z_2\otimes Z_4$	$M_{15}$, $M_{16}$, $M_{20}$, $M_{30}$
$Z_2\otimes Z_2\otimes Z_2$	$M_{24}$
$Z_{10}$	$M_{11}$, $M_{22}$
$Z_{12}$	$M_{13}$, $M_{26}$
$Z_2\otimes Z_6$	$M_{21}$, $M_{28}$, $M_{36}$, $M_{42}$
$Z_{16}$	$M_{17}$, $M_{34}$
$Z_2\otimes Z_8$	$M_{32}$
$Z_2\otimes Z_2\otimes Z_4$	$M_{40}$, $M_{48}$, $M_{60}$
$Z_{18}$	$M_{19}$, $M_{27}$, $M_{38}$, $M_{54}$
$Z_{20}$	$M_{25}$, $M_{50}$
$Z_2\otimes Z_{10}$	$M_{33}$, $M_{44}$, $M_{66}$
$Z_{22}$	$M_{23}$, $M_{46}$
$Z_2\otimes Z_{12}$	$M_{35}$, $M_{39}$, $M_{45}$, $M_{52}$, $M_{70}$, $M_{78}$, $M_{90}$
$Z_{28}$	$M_{29}$, $M_{58}$
$Z_{30}$	$M_{31}$, $M_{62}$
$Z_{36}$	$M_{37}$, $M_{74}$

The number of Characteristic Factors $r$ of $M_m$ for $m=1$, 2, ... are 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, ... (Sloane's A046072). The number of Quadratic Residues in $M_m$ for $m>2$ are given by $\phi(m)/2^r$ (Shanks 1993, p. 95). The first few for $m=1$, 2, ... are 0, 1, 1, 1, 2, 1, 3, 1, 3, 2, 5, 1, 6, ... (Sloane's A046073).

In the table below, $\phi(n)$ is the Totient Function (Sloane's A000010) factored into Characteristic Factors, $\lambda(n)$ is the Carmichael Function (Sloane's A011773), and $g_i$ are the smallest generators of the group $M_n$ (of which there is a number equal to the number of Characteristic Factors).

$n$	$\phi(n)$	$\lambda(n)$	$g_i$	$n$	$\phi(n)$	$\lambda(n)$	$g_i$
3	2	2	2	27	18	18	2
4	2	2	3	28	$2\cdot 6$	6	13, 3
5	4	2	2	29	28	28	2
6	2	2	5	30	$2\cdot 4$	4	11, 7
7	6	6	3	31	30	30	3
8	$2\cdot 2$	2	7, 3	32	$2\cdot 8$	8	31, 3
9	6	6	2	33	$2\cdot 10$	10	10, 2
10	4	4	3	34	16	16	3
11	10	10	2	35	$2\cdot 12$	12	6, 2
12	$2\cdot 2$	2	5, 7	36	$2\cdot 6$	6	19,5
13	12	12	2	37	36	36	2
14	6	6	3	38	18	18	3
15	$2\cdot 4$	4	14, 2	39	$2\cdot 12$	12	38, 2
16	$2\cdot 4$	4	15, 3	40	$2\cdot 2\cdot 4$	4	39, 11, 3
17	16	16	3	41	40	40	6
18	6	6	5	42	$2\cdot 6$	6	13, 5
19	18	18	2	43	42	42	3
20	$2\cdot 4$	4	19, 3	44	$2\cdot 10$	10	43, 3
21	$2\cdot 6$	6	20, 2	45	$2\cdot 12$	12	44, 2
22	10	10	7	46	22	22	5
23	22	22	5	47	46	46	5
24	$2\cdot 2\cdot 2$	2	5, 7, 13	48	$2\cdot 2\cdot 4$	4	47, 7, 5
25	20	20	2	49	42	42	3
26	12	12	7	50	20	20	3

See also Characteristic Factor, Cycle Graph, Finite Group, Residue Class

References

Riesel, H. ``The Structure of the Group $M_n$.'' Prime Numbers and Computer Methods for Factorization, 2nd ed. Boston, MA: Birkhäuser, pp. 270-272, 1994.

Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, pp. 61-62 and 92, 1993.

Sloane, N. J. A. Sequences A011773, A046072, A046073, and A000010/M0299 in ``An On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.

Weisstein, E. W. ``Groups.'' Mathematica notebook Groups.m.