Multiplicative group of integers modulo n

In modular arithmetic, the integers coprime (relatively prime) to "n" from the set formula_1 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 formula_2, 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: formula_3 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 (congruence classes of) integers modulo "n" with the operations of addition and multiplication is a ring.
It is denoted formula_4  or  formula_5  (the notation refers to taking the quotient of integers modulo the ideal formula_6 or formula_7 consisting of the multiples of "n").
Outside of number theory the simpler notation formula_8 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 (depending on the author) formula_9   formula_10   formula_11   formula_12   (for German "Einheit", which translates as "unit"), formula_13, or similar notations. This article uses formula_14
The notation formula_15 refers to the cyclic group of order "n".
It is isomorphic to the group of integers modulo "n" under addition.
Note that formula_4 or formula_8 may also refer to the group under addition.
For example, the multiplicative group formula_18 for a prime "p" is cyclic and hence isomorphic to the additive group formula_19, but the isomorphism is not obvious.
Structure.
The order of the multiplicative group of integers modulo "n" is the number of integers in formula_1 coprime to "n".
It is given by Euler's totient function: formula_21 .
For prime "p", formula_22.
Cyclic case.
The group formula_2 is cyclic if and only if "n" is 1, 2, 4, "p""k" or 2"p""k", 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" (a generating set {"g"} of size one), that is, the powers formula_26 give all possible residues modulo "n" coprime to "n" (the first formula_27 powers formula_28 give each exactly once).
A generator of formula_2 is called a primitive root modulo "n".
If there is any generator, then there are formula_30 of them.
Powers of 2.
Modulo 1 any two integers are congruent, i.e., there is only one congruence class, [0], coprime to 1. Therefore, formula_31 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, [1], so formula_32 is the trivial group.
Modulo 4 there are two coprime congruence classes, [1] and [3], so formula_33 the cyclic group with two elements.
Modulo 8 there are four coprime congruence classes, [1], [3], [5] and [7]. The square of each of these is 1, so formula_34 the Klein four-group.
Modulo 16 there are eight coprime congruence classes [1], [3], [5], [7], [9], [11], [13] and [15]. formula_35 is the 2-torsion subgroup (i.e., the square of each element is 1), so formula_36 is not cyclic. The powers of 3, formula_37 are a subgroup of order 4, as are the powers of 5, formula_38   Thus formula_39
The pattern shown by 8 and 16 holds for higher powers 2"k", : formula_40 is the 2-torsion subgroup (so formula_41 is not cyclic) and the powers of 3 are a cyclic subgroup of order , so formula_42
General composite numbers.
By the fundamental theorem of finite abelian groups, the group formula_2 is isomorphic to a direct product of cyclic groups of prime power orders.
More specifically, the Chinese remainder theorem says that if formula_44 then the ring formula_4 is the direct product of the rings corresponding to each of its prime power factors:
Similarly, the group of units formula_2 is the direct product of the groups corresponding to each of the prime power factors:
For each odd prime power formula_49 the corresponding factor formula_50 is the cyclic group of order formula_51, which may further factor into cyclic groups of prime-power orders.
For powers of 2 the factor formula_52 is not cyclic unless "k" = 0, 1, 2, but factors into cyclic groups as described above.
The order of the group formula_27 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 formula_54 .
In other words, formula_54 is the smallest number such that for each "a" coprime to "n", formula_56 holds.
It divides formula_27 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". (Because the residue 1 when raised to any power is congruent to 1 modulo "n", the set of such elements is nonempty.) 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 (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 . 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 (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 is a "false witness" for any odd composite "n".
"n" = 91.
For "n" = 91 (= 7 × 13), there are formula_58 residues coprime to 91, half of them (i.e., 36 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", "x"90 is congruent to 1 mod 91.
"n" = 561.
"n" = 561 (= 3 × 11 × 17) is a Carmichael number, thus "s"560 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 formula_2 and a generating set for "n" ≤ 128. The decomposition and generating sets are not unique; for example, formula_60 (but formula_61). The table below lists the shortest decomposition (among those, the lexicographically first is chosen – this guarantees isomorphic groups are listed with the same decompositions). 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 formula_62. Then formula_63 means that the order of the group is 8 (i.e., there are 8 numbers less than 20 and coprime to it); formula_64 means the order of each element divides 4, that is, the fourth power of any number coprime to 20 is congruent to 1 (mod 20). The set {3,19} generates the group, which means that every element of formula_62 is of the form (where "a" is 0, 1, 2, or 3, because the element 3 has order 4, and similarly "b" is 0 or 1, because the element 19 has order 2).
Smallest primitive root mod "n" are (0 if no root exists)
Numbers of the elements in a minimal generating set of mod "n" are
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.