In modular arithmetic, the integers coprime (relatively prime) 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
It is used in cryptography, integer factorization, and primality testing.
It is an abelian, finite group whose order is given by Euler's totient function:
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.
Thus the notion of congruence classes modulo n that are coprime to n is well-defined.
Finally, given a, the multiplicative inverse of a modulo n is an integer x satisfying ax ≡ 1 (mod n).
It exists precisely when a is coprime to n, because in that case gcd(a, n) = 1 and by Bézout's lemma there are integers x and y satisfying ax + ny = 1.
Notice that the equation ax + ny = 1 implies that x is coprime to n, so the multiplicative inverse belongs to the group.
The set of (congruence classes of) integers modulo n with the operations of addition and multiplication is a ring.
(the notation refers to taking the quotient of integers modulo the ideal
for a prime p is cyclic and hence isomorphic to the additive group
Modulo 1 any two integers are congruent, i.e., there is only one congruence class, [0], coprime to 1.
is isomorphic to a direct product of cyclic groups of prime power orders.
is the direct product of the rings corresponding to each of its prime power factors: Similarly, the group of units
, which may further factor into cyclic groups of prime-power orders.
, called the "group of false witnesses", comprising the solutions of the equation
, the elements which, raised to the power n − 1, are congruent to 1 modulo n.[8] Fermat's Little Theorem states that for n = p a prime, this group consists of all
; thus for n composite, such residues x are "false positives" or "false witnesses" for the primality of n. The number x = 2 is most often used in this basic primality check, and n = 341 = 11 × 31 is notable since
, and n = 341 is the smallest composite number for which x = 2 is a false witness to primality.
In fact, the false witnesses subgroup for 341 contains 100 elements, and is of index 3 inside the 300-element group
The smallest example with a nontrivial subgroup of false witnesses is 9 = 3 × 3.
The same argument shows that n − 1 is a "false witness" for any odd composite n. For n = 91 (= 7 × 13), there are
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, x90 is congruent to 1 mod 91. n = 561 (= 3 × 11 × 17) 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.
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.
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
Smallest primitive root mod n are (0 if no root exists) Numbers of the elements in a minimal generating set of mod n are 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.