Multiplicative group of integers modulo n

Not to be confused with Integers modulo n.

In modular arithmetic the set of congruence classes relatively prime to the modulus number, say n, form a group under multiplication called the multiplicative group of integers modulo n. It is also called the group of primitive residue classes modulo n. In the theory of rings, a branch of abstract algebra, it is described as the group of units of the ring of integers modulo n. (Units refers to elements with a multiplicative inverse.)

This group is fundamental in number theory. It has found applications in cryptography, integer factorization, and primality testing. For example, by finding the order of this group, one can determine whether n is prime: n is prime if and only if the order is n − 1.

Group axioms

It is a straightforward exercise to show that, under multiplication, the set of congruence classes modulo n that are relatively prime to n satisfy the axioms for an abelian group.

Because a ≡ b (mod n) implies that gcd(a, n) = gcd(b, n), the notion of congruence classes modulo n that are relatively prime to n is well-defined.

Since gcd(a, n) = 1 and gcd(b, n) = 1 implies gcd(ab, n) = 1 the set of classes relatively prime to n is closed under multiplication.

The natural mapping from the integers to the congruence classes modulo n that takes an integer to its congruence class modulo n respects products. This implies that the class containing 1 is the unique multiplicative identity, and also the associative and commutative laws hold. In fact it is a ring homomorphism.

Given a, gcd(a, n) = 1, finding x satisfying ax ≡ 1 (mod n) is the same as solving ax + ny = 1, which can be done by Bézout's lemma. The x found will have the property that gcd(x, n) = 1.

Notation

The (quotient) ring of integers modulo n is denoted $\mathbb{Z}/n\mathbb{Z}$ or $\mathbb{Z}/(n)$ (i.e., the ring of integers modulo the ideal $n\mathbb{Z} = (n)$ consisting of the multiples of n) or by $\mathbb{Z}_n$ (though the latter can be confused with the $p$ -adic integers when n is a prime number). Depending on the author, its group of units may be written $(\mathbb{Z}/n\mathbb{Z})^*,$ $(\mathbb{Z}/n\mathbb{Z})^\times,$ $\mathrm{U}(\mathbb{Z}/n\mathbb{Z}),$ $\mathrm{E}(\mathbb{Z}/n\mathbb{Z})$ (for German Einheit, which translates as unit) or similar notations. This article uses $(\mathbb{Z}/n\mathbb{Z})^\times.$

The notation $\mathrm{C}_n$ refers to the cyclic group of order n.

Structure

n = 1

Modulo 1 any two integers are congruent, i.e. there is only one congruence class. Every integer is relatively prime to 1. Therefore the single congruence class modulo 1 is relatively prime to the modulus, so $(\mathbb{Z}/1\,\mathbb{Z})^\times \cong \mathrm{C}_1$ is trivial. This implies that φ(1) = 1. Since the first power of any integer is congruent to 1 modulo 1, λ(1) is also 1.

Because of its trivial nature, the case of congruences modulo 1 is generally ignored. For example, the theorem " $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic if and only if φ(n) = λ(n)" implicitly includes the case n = 1, whereas the usual statement of Gauss's theorem " $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic if and only if n = 2, 4, any power of an odd prime or twice any power of an odd prime," explicitly excludes 1.

Powers of 2

Modulo 2 there is only one relatively prime congruence class, 1, so $(\mathbb{Z}/2\mathbb{Z})^\times \cong \mathrm{C}_1$ is the trivial group.

Modulo 4 there are two relatively prime congruence classes, 1 and 3, so $(\mathbb{Z}/4\mathbb{Z})^\times \cong \mathrm{C}_2,$ the cyclic group with two elements.

Modulo 8 there are four relatively prime classes, 1, 3, 5 and 7. The square of each of these is 1, so $(\mathbb{Z}/8\mathbb{Z})^\times \cong \mathrm{C}_2 \times \mathrm{C}_2,$ the Klein four-group.

Modulo 16 there are eight relatively prime classes 1, 3, 5, 7, 9, 11, 13 and 15. $\{\pm 1, \pm 7\}\cong \mathrm{C}_2 \times \mathrm{C}_2,$ is the 2-torsion subgroup (i.e. the square of each element is 1), so $(\mathbb{Z}/16\mathbb{Z})^\times$ is not cyclic. The powers of 3, $\{1, 3, 9, 11\}$ are a subgroup of order 4, as are the powers of 5, $\{1, 5, 9, 13\}.$ Thus $(\mathbb{Z}/16\mathbb{Z})^\times \cong \mathrm{C}_2 \times \mathrm{C}_4.$

The pattern shown by 8 and 16 holds^[1] for higher powers 2^k, k > 2: $\{\pm 1, 2^{k-1} \pm 1\}\cong \mathrm{C}_2 \times \mathrm{C}_2,$ is the 2-torsion subgroup (so $(\mathbb{Z}/2^k\mathbb{Z})^\times$ is not cyclic) and the powers of 3 are a subgroup of order 2^{k − 2}, so $(\mathbb{Z}/2^k\mathbb{Z})^\times \cong \mathrm{C}_2 \times \mathrm{C}_{2^{k-2}}.$

Powers of odd primes

For powers of odd primes p^k the group is cyclic:^[2]^[3]

(\mathbb{Z}/p^k\mathbb{Z})^\times \cong \mathrm{C}_{p^{k-1}(p-1)} \cong \mathrm{C}_{\varphi(p^k)} .

General composite numbers

The Chinese remainder theorem^[4] says that if $\;\;n=p_1^{k_1}p_2^{k_2}p_3^{k_3}\dots, \;$ then the ring $\mathbb{Z}/n\mathbb{Z}$ is the direct product of the rings corresponding to each of its prime power factors:

\mathbb{Z}/n\mathbb{Z} \cong \mathbb{Z}/{p_1^{k_1}}\mathbb{Z}\; \times \;\mathbb{Z}/{p_2^{k_2}}\mathbb{Z} \;\times\; \mathbb{Z}/{p_3^{k_3}}\mathbb{Z}\dots\;\;

Similarly, the group of units $(\mathbb{Z}/n\mathbb{Z})^\times$ is the direct product of the groups corresponding to each of the prime power factors:

(\mathbb{Z}/n\mathbb{Z})^\times\cong (\mathbb{Z}/{p_1^{k_1}}\mathbb{Z})^\times \times (\mathbb{Z}/{p_2^{k_2}}\mathbb{Z})^\times \times (\mathbb{Z}/{p_3^{k_3}}\mathbb{Z})^\times \dots\;.

Subgroup of false witnesses

If n is composite, there exists a subgroup of the multiplicative group, called the "group of false witnesses", in which the elements, when raised to the power n − 1, are congruent to 1 modulo n (since the residue 1, to any power, is congruent to 1 modulo n, the set of such elements is nonempty).^[5] One could say, because of Fermat's Little Theorem, that such residues are "false positives" or "false witnesses" for the primality of n. 2 is the residue most often used in this basic primality check, hence 341 = 11 × 31 is famous since 2³⁴⁰ is congruent to 1 modulo 341, and 341 is the smallest such composite number (with respect to 2). For 341, the false witnesses subgroup contains 100 residues and so is of index 3 inside the 300 element multiplicative group mod 341.

Examples

n = 9

The smallest example with a nontrivial subgroup of false witnesses is 9 = 3 × 3. There are 6 residues relatively prime to 9: 1, 2, 4, 5, 7, 8. Since 8 is congruent to −1 modulo 9, it follows that 8⁸ is congruent to 1 modulo 9. So 1 and 8 are false positives for the "primality" of 9 (since 9 is not actually prime). These are in fact the only ones, so the subgroup {1,8} is the subgroup of false witnesses. The same argument shows that n − 1 is a "false witness" for any odd composite n.

n = 561

561 is a Carmichael number, thus n⁵⁶⁰ is congruent to 1 modulo 561 for any number n coprime to 561. Thus the subgroup of false witnesses is in this case not proper, it is the entire group of multiplicative units modulo 561, which consists of 320 residues.

Properties

Order

The order of the group is given by Euler's totient function: $| (\mathbb{Z}/n\mathbb{Z})^\times|=\varphi(n).$ This is the product of the orders of the cyclic groups in the direct product. (sequence A000010 in OEIS)

Exponent

The exponent is given by the Carmichael function $\lambda(n),$ the least common multiple of the orders of the cyclic groups. Thus, $\lambda(n)$ is the smallest number for a given n such that for each a relatively prime to n, $a^{\lambda(n)} \equiv 1 \pmod n$ holds. (sequence A002322 in OEIS)

Generators

The group $(\mathbb{Z}/n\mathbb{Z})^\times$ is cyclic if and only if its order $\varphi(n)$ is equal to its exponent $\lambda(n)$ . This is the case when n is 1, 2, 4, p^k or 2p^k, where p is an odd prime and k > 0. For all other values of n the group is not cyclic.^[6]^[7]^[3] The single generator in the cyclic case is called a primitive root modulo n.^[8]

Since all the $(\mathbb{Z}/n\mathbb{Z})^\times,$ n ≤ 7 are cyclic, another way to state this is: If n < 8 then $(\mathbb{Z}/n\mathbb{Z})^\times$ has a primitive root. If n ≥ 8 then $(\mathbb{Z}/n\mathbb{Z})^\times$ has a primitive root unless n is divisible by 4 or by two distinct odd primes.^[9] All ns which have a primitive root are listed in A033948.

In the general case there is one generator for each cyclic direct factor.

Examples

This table shows the cyclic decomposition of $(\mathbb{Z}/n\mathbb{Z})^\times$ and a generating set for n ≤ 128. The generating sets are not unique; e.g. modulo 16 both {15, 3} and {15, 5} will work, in the list, we list the smallest values, (thus, for n with primitive root, we list the smallest primitive root modulo n) for example, for modulo 12, we list {5, 7} instead of {5, 11} or {7, 11} . The generators are listed in the same order as the direct factors.

For example, we take n = 20. $\varphi(20)=8$ means that the order of $(\mathbb{Z}/20\mathbb{Z})^\times$ is 8 (i.e. there are 8 numbers less than 20 and coprime to it); $\lambda(20)=4$ that the fourth power of any number relatively prime to 20 is congruent to 1 (mod 20); and as for the generators, 19 has order 2, 3 has order 4, and every member of $(\mathbb{Z}/20\mathbb{Z})^\times$ is of the form 19^a × 3^b, where a is 0 or 1 and b is 0, 1, 2, or 3.

The powers of 19 are {±1} and the powers of 3 are {3, 9, 7, 1}. The latter and their negatives modulo 20, {17, 11, 13, 19} are all the numbers less than 20 and coprime to it. That the order of 19 is 2 and the order of 3 is 4 implies that the fourth power of every member of $(\mathbb{Z}/20\mathbb{Z})^\times$ is congruent to 1 (mod 20).

Smallest primitive root mod n are (0 if no root exists)

0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, 0, 0, 0, 3, 0, 2, 7, 2, 0, 0, 3, 0, 0, 3, 0, ... (sequence A046145 in OEIS)

Numbers of the elements in generating set of mod n are

1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 3, 1, 2, 1, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 3, 1, 1, 1, 3, 2, 1, 2, 3, 1, 2, ... (sequence A046072 in OEIS)

Group Structure of **(Z/nZ)^×**
$n\;$	$(\mathbb{Z}/n\mathbb{Z})^\times$	$\varphi(n)$	$\lambda(n)\;$	generating set	$n\;$	$(\mathbb{Z}/n\mathbb{Z})^\times$	$\varphi(n)$	$\lambda(n)\;$	generating set	$n\;$	$(\mathbb{Z}/n\mathbb{Z})^\times$	$\varphi(n)$	$\lambda(n)\;$	generating set	$n\;$	$(\mathbb{Z}/n\mathbb{Z})^\times$	$\varphi(n)$	$\lambda(n)\;$	generating set
1	C₁	1	1	0	33	C₂×C₁₀	20	10	2, 10	65	C₄×C₁₂	48	12	2, 12	97	C₉₆	96	96	5
2	C₁	1	1	1	34	C₁₆	16	16	3	66	C₂×C₁₀	20	10	5, 7	98	C₄₂	42	42	3
3	C₂	2	2	2	35	C₂×C₁₂	24	12	2, 6	67	C₆₆	66	66	2	99	C₂×C₃₀	60	30	2, 5
4	C₂	2	2	3	36	C₂×C₆	12	6	5, 19	68	C₂×C₁₆	32	16	3, 67	100	C₂×C₂₀	40	20	3, 99
5	C₄	4	4	2	37	C₃₆	36	36	2	69	C₂×C₂₂	44	22	2, 68	101	C₁₀₀	100	100	2
6	C₂	2	2	5	38	C₁₈	18	18	3	70	C₂×C₁₂	24	12	3, 11	102	C₂×C₁₆	32	16	5, 7
7	C₆	6	6	3	39	C₂×C₁₂	24	12	2, 38	71	C₇₀	70	70	7	103	C₁₀₂	102	102	5
8	C₂×C₂	4	2	3, 7	40	C₂×C₂×C₄	16	4	3, 11, 39	72	C₂×C₂×C₆	24	6	5, 7, 11	104	C₂×C₂×C₁₂	48	12	3, 5, 103
9	C₆	6	6	2	41	C₄₀	40	40	6	73	C₇₂	72	72	5	105	C₂×C₂×C₁₂	48	12	2, 11, 104
10	C₄	4	4	3	42	C₂×C₆	12	6	5, 13	74	C₃₆	36	36	5	106	C₅₂	52	52	3
11	C₁₀	10	10	2	43	C₄₂	42	42	3	75	C₂×C₂₀	40	20	2, 74	107	C₁₀₆	106	106	2
12	C₂×C₂	4	2	5, 7	44	C₂×C₁₀	20	10	3, 43	76	C₂×C₁₈	36	18	3, 75	108	C₂×C₁₈	36	18	5, 107
13	C₁₂	12	12	2	45	C₂×C₁₂	24	12	2, 44	77	C₂×C₃₀	60	30	2, 76	109	C₁₀₈	108	108	6
14	C₆	6	6	3	46	C₂₂	22	22	5	78	C₂×C₁₂	24	12	5, 7	110	C₂×C₂₀	40	20	2, 109
15	C₂×C₄	8	4	2, 13	47	C₄₆	46	46	5	79	C₇₈	78	78	3	111	C₂×C₃₆	72	36	2, 5
16	C₂×C₄	8	4	3, 15	48	C₂×C₂×C₄	16	4	5, 7, 47	80	C₂×C₄×C₄	32	4	3, 7, 79	112	C₂×C₂×C₁₂	48	12	3, 5, 111
17	C₁₆	16	16	3	49	C₄₂	42	42	3	81	C₅₄	54	54	2	113	C₁₁₂	112	112	3
18	C₆	6	6	5	50	C₂₀	20	20	3	82	C₄₀	40	40	7	114	C₂×C₁₈	36	18	3, 113
19	C₁₈	18	18	2	51	C₂×C₁₆	32	16	5, 50	83	C₈₂	82	82	2	115	C₂×C₄₄	88	44	2, 114
20	C₂×C₄	8	4	3, 19	52	C₂×C₁₂	24	12	7, 51	84	C₂×C₂×C₆	24	6	5, 11, 13	116	C₂×C₂₈	56	28	3, 115
21	C₂×C₆	12	6	2, 20	53	C₅₂	52	52	2	85	C₄×C₁₆	64	16	2, 3	117	C₆×C₁₂	72	12	2, 5
22	C₁₀	10	10	7	54	C₁₈	18	18	5	86	C₄₂	42	42	3	118	C₅₈	58	58	11
23	C₂₂	22	22	5	55	C₂×C₂₀	40	20	2, 21	87	C₂×C₂₈	56	28	2, 86	119	C₂×C₄₈	96	48	2, 118
24	C₂×C₂×C₂	8	2	5, 7, 13	56	C₂×C₂×C₆	24	6	3, 13, 29	88	C₂×C₂×C₁₀	40	10	3, 5, 7	120	C₂×C₂×C₂×C₄	32	4	7, 11, 13, 19
25	C₂₀	20	20	2	57	C₂×C₁₈	36	18	2, 20	89	C₈₈	88	88	3	121	C₁₁₀	110	110	2
26	C₁₂	12	12	7	58	C₂₈	28	28	3	90	C₂×C₁₂	24	12	7, 11	122	C₆₀	60	60	7
27	C₁₈	18	18	2	59	C₅₈	58	58	2	91	C₆×C₁₂	72	12	2, 3	123	C₂×C₄₀	80	40	2, 5
28	C₂×C₆	12	6	3, 13	60	C₂×C₂×C₄	16	4	7, 11, 19	92	C₂×C₂₂	44	22	3, 91	124	C₂×C₃₀	60	30	3, 123
29	C₂₈	28	28	2	61	C₆₀	60	60	2	93	C₂×C₃₀	60	30	5, 11	125	C₁₀₀	100	100	2
30	C₂×C₄	8	4	7, 11	62	C₃₀	30	30	3	94	C₄₆	46	46	5	126	C₆×C₆	36	6	5, 7
31	C₃₀	30	30	3	63	C₆×C₆	36	6	2, 5	95	C₂×C₃₆	72	36	2, 3	127	C₁₂₆	126	126	3
32	C₂×C₈	16	8	3, 31	64	C₂×C₁₆	32	16	3, 63	96	C₂×C₂×C₈	32	8	5, 7, 95	128	C₂×C₃₂	64	32	3, 127

Notes

↑ (Gauss & Clarke 1986, arts. 90–91)
↑ (Gauss & Clarke 1986, arts. 52–56, 82–891)
1 2 (Vinogradov 2003, pp. 105-121, § VI PRIMITIVE ROOTS AND INDICES)
↑ Riesel covers all of this. (Riesel 1994, pp. 267–275)
↑ Erdős, Paul; Pomerance, Carl (1986). "On the number of false witnesses for a composite number". Math. Comput. 46: 259–279. doi:10.1090/s0025-5718-1986-0815848-x. Zbl 0586.10003.
↑ Weisstein, Eric W., "Modulo Multiplication Group", MathWorld.
↑ Primitive root, Encyclopedia of Mathematics
↑ (Vinogradov 2003, p. 106)
↑ (Vinogradov 2003, pp. 116f)

References

The Disquisitiones Arithmeticae has been translated from Gauss's Ciceronian Latin into English and German. The German edition includes all of his papers on number theory: all the proofs of quadratic reciprocity, the determination of the sign of the Gauss sum, the investigations into biquadratic reciprocity, and unpublished notes.

Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithmeticae (Second, corrected edition), New York: Springer, ISBN 0-387-96254-9
Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0-8284-0191-8
Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 0-8176-3743-5
Vinogradov, I. M. (2003), "§ VI PRIMITIVE ROOTS AND INDICES", Elements of Number Theory, Mineola, NY: Dover Publications, pp. 105–121, ISBN 0-486-49530-2

External links

Weisstein, Eric W., "Modulo Multiplication Group", MathWorld.
Weisstein, Eric W., "Primitive Root", MathWorld.
Calculator for n = 2 to 50 by Shing Hing Man

This article is issued from Wikipedia - version of the Wednesday, January 27, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Multiplicative group of integers modulo n

Group axioms

Notation

Structure

n = 1

Powers of 2

Powers of odd primes

General composite numbers

Subgroup of false witnesses

Examples

Properties

Order

Exponent

Generators

Examples

See also

Notes

References

External links