TOPICS
Search

Modulo Multiplication Group


A modulo multiplication group is a finite group M_m of residue classes prime to m under multiplication mod m. M_m is Abelian of group order phi(m), where phi(m) is the totient function.

ModuloMultiplicationGroups

A modulo multiplication group can be visualized by constructing its cycle graph. Cycle graphs are illustrated above for some low-order modulo multiplication groups. Such graphs are constructed by drawing labeled nodes, one for each element A of the residue class, and connecting cycles obtained by iterating A^n. Each edge of such a graph is bidirected, but they are commonly drawn using undirected edges with double edges used to indicate cycles of length two (Shanks 1993, pp. 85 and 87-92).

The following table gives the modulo multiplication groups of small orders, together with their isomorphisms with respect to cyclic groups C_n.

M_mgroupphi(m)elements
M_2<e>21
M_3C_221, 2
M_4C_221, 3
M_5C_441, 2, 3, 4
M_6C_221, 5
M_7C_661, 2, 3, 4, 5, 6
M_8C_2×C_241, 3, 5, 7
M_9C_661, 2, 4, 5, 7, 8
M_(10)C_441, 3, 7, 9
M_(11)C_(10)101, 2, 3, 4, 5, 6, 7, 8, 9, 10
M_(12)C_2×C_241, 5, 7, 11
M_(13)C_(12)121, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
M_(14)C_661, 3, 5, 9, 11, 13
M_(15)C_2×C_481, 2, 4, 7, 8, 11, 13, 14
M_(16)C_2×C_481, 3, 5, 7, 9, 11, 13, 15
M_(17)C_(16)161, 2, 3, ..., 16
M_(18)C_661, 5, 7, 11, 13, 17
M_(19)C_(18)181, 2, 3, ..., 18
M_(20)C_2×C_481, 3, 7, 9, 11, 13, 17, 19
M_(21)C_2×C_6121, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20
M_(22)C_(10)101, 3, 5, 7, 9, 13, 15, 17, 19, 21
M_(23)C_(22)221, 2, 3, ..., 22
M_(24)C_2×C_2×C_281, 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>=1 (Shanks 1993, p. 92). The first few of these are m=3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17, 18, 19, ... (OEIS A033948; Shanks 1993, p. 84).

The only ordered m for which the elements of M_m are all self-conjugate are the divisors of 24: 1, 2, 3, 4, 6, 8, 12, 24 (OEIS A018253; Eggar 2000). These correspond to the groups <e>, C_2, C_2×C_2, and C_2×C_2×C_2. This also means that no modulo multiplication group is isomorphic to a direct product of more than three copies of C_2.

Isomorphic modulo multiplication groups can be determined using a particular type of factorization of the totient function phi(m) using the property that

 phi(p^alpha)=p^(alpha-1)(p-1)
(1)

as described by Shanks (1993, pp. 92-93). To perform this factorization, begin by analogy with computation of the totient function by factoring m in the standard form

 m=p_1^(a_1)p_2^(a_2)...p_n^(a_n).
(2)

Now for each power of an odd prime, write

 phi(p_i^(a_i))=(p_i-1)p_i^(a_i-1),
(3)

and factor the leading term

 p_i-1=q_1^(b_1)q_2^(b_2)...q_s^(b_s)
(4)

as

 <q_1^(b_1)><q_2^(b_2)>...<q_s^(b_s)><p_i^(a_i-1)>,
(5)

where <q^b> denotes the explicit expansion of q^b (i.e., 5^2=25), and the last term is omitted if a_i=1 (since in that case, <p_i^(a_i-1)>=1).

If m contains a power of 2 so that p_1=2, then write

 phi(2^(a_1))={nothing   for a_1<2; <2>   for a_1=2; <2><2^(a_1-2)>   for a_1>2.
(6)

Now combine terms from the odd and even primes, write them as a product and combine any unambiguous products of terms. The resulting expression is denoted phi_m and the group M_m is isomorphic to a direct product of cyclic groups of orders given by phi_m.

For example, consider the modulo multiplication group of order m=104=2^3·13. The only odd prime factor is 13, so factoring gives 13-1=12=<2^2><3>=3·4. 104 contains a factor of 2^3, so the rule for even prime factors gives <2><2^(3-2)>=<2><2>=2·2. Combining these two gives phi_(104)=2·2·3·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 group 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×3=12, leaving 2·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·2·12, and the group M_m is isomorphic to C_2×C_2×C_(12).

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 the cyclic group C_8, quaternion group Q_8, or the dihedral group 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).

The following table gives the orders of modulo multiplication groups M_m that are isomorphic to direct products of cyclic groups for m<=50.

groupisomorphic M_m
<e>M_2
C_2M_3, M_4, M_6
C_4M_5, M_(10)
C_2×C_2M_8, M_(12)
C_6M_7, M_9, M_(14), M_(18)
C_2×C_4M_(15), M_(16), M_(20), M_(30)
C_2×C_2×C_2M_(24)
C_(10)M_(11), M_(22)
C_(12)M_(13), M_(26)
C_2×C_6M_(21), M_(28), M_(36), M_(42)
C_(16)M_(17), M_(34)
C_2×C_8M_(32)
C_2×C_2×C_4M_(40), M_(48)
C_(18)M_(19), M_(27), M_(38)
C_(20)M_(25), M_(50)
C_2×C_(10)M_(33), M_(44)
C_(22)M_(23), M_(46)
C_2×C_(12)M_(35), M_(39), M_(45)
C_(28)M_(29)
C_(30)M_(31)
C_(36)M_(37)
C_(40)M_(41)
C_(42)M_(43), M_(49)
C_(46)M_(47)

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, ... (OEIS 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, ... (OEIS A046073).

In the table below, phi(n) is the totient function (OEIS A000010) factored into characteristic factors, lambda(n) is the Carmichael function (OEIS 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).

nphi(n)lambda(n)g_inphi(n)lambda(n)g_i
32222718182
4223282·6613, 3
54422928282
6225302·4411, 7
76633130303
82·227, 3322·8831, 3
9662332·101010, 2
104433416163
1110102352·12126, 2
122·225, 7362·6619,5
13121223736362
146633818183
152·4414, 2392·121238, 2
162·4415, 3402·2·4439, 11, 3
17161634140406
18665422·6613, 5
19181824342423
202·4419, 3442·101043, 3
212·6620, 2452·121244, 2
22101074622225
23222254746465
242·2·225, 7, 13482·2·4447, 7, 5
25202024942423
26121275020203

See also

Characteristic Factor, Cycle Graph, Finite Group, Residue Class, Quadratic Residue

Explore with Wolfram|Alpha

References

Eggar, M. H. "A Curious Property of the Integer 24." Math. Gaz. 84, 96-97, March 2000.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 A000010/M0299, A011773, A018253, A033948, A046072, and A046073 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Modulo Multiplication Group

Cite this as:

Weisstein, Eric W. "Modulo Multiplication Group." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/ModuloMultiplicationGroup.html

Subject classifications