Multiplicative group of integers modulo n


In modular arithmetic, the integers coprime to n from the set of n non-negative integers form a group under multiplication modulo n, called the multiplicative group of integers modulo n. Equivalently, the elements of this group can be thought of as the congruence classes, also known as residues modulo n, that are coprime to n.
Hence another name is 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. Here units refers to elements with a multiplicative inverse, which in this ring are exactly those coprime to n.
This group, usually denoted, is fundamental in number theory. It has found applications in cryptography, integer factorization, and primality testing. It is an abelian, finite group whose order is given by Euler's totient function: For prime n the group is cyclic and in general the structure is easy to describe, though even for prime n no general formula for finding generators is known.

Group axioms

It is a straightforward exercise to show that, under multiplication, the set of congruence classes modulo n that are coprime to n satisfy the axioms for an abelian group.
Indeed, a is coprime to n if and only if. Integers in the same congruence class satisfy, hence one is coprime to n if and only if the other is. Thus the notion of congruence classes modulo n that are coprime to n is well-defined.
Since and implies, the set of classes coprime to n is closed under multiplication.
Integer multiplication respects the congruence classes, that is, and implies.
This implies that the multiplication is associative, commutative, and that the class of 1 is the unique multiplicative identity.
Finally, given a, the multiplicative inverse of a modulo n is an integer x satisfying.
It exists precisely when a is coprime to n, because in that case and by Bézout's lemma there are integers x and y satisfying. Notice that the equation implies that x is coprime to n, so the multiplicative inverse belongs to the group.

Notation

The set of integers modulo n with the operations of addition and multiplication is a ring.
It is denoted or .
Outside of number theory the simpler notation is often used, though it can be confused with the -adic integers when n is a prime number.
The multiplicative group of integers modulo n, which is the group of units in this ring, may be written as ,, or similar notations. This article uses
The notation refers to the cyclic group of order n.
It is isomorphic to the group of integers modulo n under addition.
Note that or may also refer to the group under addition.
For example, the multiplicative group for a prime p is cyclic and hence isomorphic to the additive group, but the isomorphism is not obvious.

Structure

The order of the multiplicative group of integers modulo n is the number of integers in coprime to n.
It is given by Euler's totient function: .
For prime p,.

Cyclic case

The group is cyclic if and only if n is 1, 2, 4, pk or 2pk, where p is an odd prime and. For all other values of n the group is not cyclic.
This was first proved by Gauss.
This means that for these n:
By definition, the group is cyclic if and only if it has a generator g, that is, the powers give all possible residues modulo n coprime to n.
A generator of is called a primitive root modulo n.
If there is any generator, then there are of them.

Powers of 2

Modulo 1 any two integers are congruent, i.e., there is only one congruence class, , coprime to 1. Therefore, is the trivial group with element. Because of its trivial nature, the case of congruences modulo 1 is generally ignored and some authors choose not to include the case of n = 1 in theorem statements.
Modulo 2 there is only one coprime congruence class, , so is the trivial group.
Modulo 4 there are two coprime congruence classes, and , so the cyclic group with two elements.
Modulo 8 there are four coprime congruence classes, , , and . The square of each of these is 1, so the Klein four-group.
Modulo 16 there are eight coprime congruence classes , , , , , , and . is the 2-torsion subgroup, so is not cyclic. The powers of 3, are a subgroup of order 4, as are the powers of 5, Thus
The pattern shown by 8 and 16 holds for higher powers 2k, : is the 2-torsion subgroup and the powers of 3 are a cyclic subgroup of order, so

General composite numbers

By the fundamental theorem of finite abelian groups, the group is isomorphic to a direct product of cyclic groups of prime power orders.
More specifically, the Chinese remainder theorem says that if then the ring is the direct product of the rings corresponding to each of its prime power factors:
Similarly, the group of units is the direct product of the groups corresponding to each of the prime power factors:
For each odd prime power the corresponding factor is the cyclic group of order, which may further factor into cyclic groups of prime-power orders.
For powers of 2 the factor is not cyclic unless k = 0, 1, 2, but factors into cyclic groups as described above.
The order of the group is the product of the orders of the cyclic groups in the direct product.
The exponent of the group, that is, the least common multiple of the orders in the cyclic groups, is given by the Carmichael function .
In other words, is the smallest number such that for each a coprime to n, holds.
It divides and is equal to it if and only if the group is cyclic.

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, are congruent to 1 modulo n. One could say, because of Fermat's Little Theorem, that such residues are "false positives" or "false witnesses" for the primality of n. The number 2 is the residue most often used in this basic primality check, hence is famous since 2340 is congruent to 1 modulo 341, and 341 is the smallest such composite number. 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. There are 6 residues coprime to 9: 1, 2, 4, 5, 7, 8. Since 8 is congruent to, it follows that 88 is congruent to 1 modulo 9. So 1 and 8 are false positives for the "primality" of 9. These are in fact the only ones, so the subgroup is the subgroup of false witnesses. The same argument shows that is a "false witness" for any odd composite n.

''n'' = 91

For n = 91, there are residues coprime to 91, half of them are false witnesses of 91, namely 1, 3, 4, 9, 10, 12, 16, 17, 22, 23, 25, 27, 29, 30, 36, 38, 40, 43, 48, 51, 53, 55, 61, 62, 64, 66, 68, 69, 74, 75, 79, 81, 82, 87, 88, and 90, since for these values of x, x90 is congruent to 1 mod 91.

''n'' = 561

n = 561 is a Carmichael number, thus s560 is congruent to 1 modulo 561 for any integer s coprime to 561. 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.

Examples

This table shows the cyclic decomposition of and a generating set for n ≤ 128. The decomposition and generating sets are not unique; for example, . The table below lists the shortest decomposition. The generating set is also chosen to be as short as possible, and for n with primitive root, the smallest primitive root modulo n is listed.
For example, take. Then means that the order of the group is 8 ; means the order of each element divides 4, that is, the fourth power of any number coprime to 20 is congruent to 1. The set generates the group, which means that every element of is of the form .
Smallest primitive root mod n are
Numbers of the elements in a minimal generating set of mod n are

Generating set Generating set Generating set Generating set
1C1110 33C2×C1020102, 10 65C4×C1248122, 12 97C9696965
2C1111 34C1616163 66C2×C1020105, 7 98C4242423
3C2222 35C2×C1224122, 6 67C6666662 99C2×C3060302, 5
4C2223 36C2×C61265, 19 68C2×C1632163, 67 100C2×C2040203, 99
5C4442 37C3636362 69C2×C2244222, 68 101C1001001002
6C2225 38C1818183 70C2×C1224123, 69 102C2×C1632165, 101
7C6663 39C2×C1224122, 38 71C7070707 103C1021021025
8C2×C2423, 5 40C2×C2×C41643, 11, 39 72C2×C2×C62465, 17, 19 104C2×C2×C1248123, 5, 103
9C6662 41C4040406 73C7272725 105C2×C2×C1248122, 29, 41
10C4443 42C2×C61265, 13 74C3636365 106C5252523
11C1010102 43C4242423 75C2×C2040202, 74 107C1061061062
12C2×C2425, 7 44C2×C1020103, 43 76C2×C1836183, 37 108C2×C1836185, 107
13C1212122 45C2×C1224122, 44 77C2×C3060302, 76 109C1081081086
14C6663 46C2222225 78C2×C1224125, 7 110C2×C2040203, 109
15C2×C4842, 14 47C4646465 79C7878783 111C2×C3672362, 110
16C2×C4843, 15 48C2×C2×C41645, 7, 47 80C2×C4×C43243, 7, 79 112C2×C2×C1248123, 5, 111
17C1616163 49C4242423 81C5454542 113C1121121123
18C6665 50C2020203 82C4040407 114C2×C1836185, 37
19C1818182 51C2×C1632165, 50 83C8282822 115C2×C4488442, 114
20C2×C4843, 19 52C2×C1224127, 51 84C2×C2×C62465, 11, 13 116C2×C2856283, 115
21C2×C61262, 20 53C5252522 85C4×C1664162, 3 117C6×C1272122, 17
22C1010107 54C1818185 86C4242423 118C58585811
23C2222225 55C2×C2040202, 21 87C2×C2856282, 86 119C2×C4896483, 118
24C2×C2×C2825, 7, 13 56C2×C2×C62463, 13, 29 88C2×C2×C1040103, 5, 7 120C2×C2×C2×C43247, 11, 19, 29
25C2020202 57C2×C1836182, 20 89C8888883 121C1101101102
26C1212127 58C2828283 90C2×C1224127, 11 122C6060607
27C1818182 59C5858582 91C6×C1272122, 3 123C2×C4080407, 83
28C2×C61263, 13 60C2×C2×C41647, 11, 19 92C2×C2244223, 91 124C2×C3060303, 61
29C2828282 61C6060602 93C2×C30603011, 61 125C1001001002
30C2×C4847, 11 62C3030303 94C4646465 126C6×C63665, 13
31C3030303 63C6×C63662, 5 95C2×C3672362, 94 127C1261261263
32C2×C81683, 31 64C2×C1632163, 63 96C2×C2×C83285, 17, 31 128C2×C3264323, 127