# Multiplicative group of integers modulo n

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 gcd(*a*, *n*) = 1. Integers in the same congruence class *a* ≡ *b* (mod *n*) satisfy gcd(*a*, *n*) = gcd(*b*, *n*), 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 gcd(*a*, *n*) = 1 and gcd(*b*, *n*) = 1 implies gcd(*ab*, *n*) = 1, the set of classes coprime to *n* is closed under multiplication.

Integer multiplication respects the congruence classes, that is, *a* ≡ *a' * and *b* ≡ *b' * (mod *n*) implies *ab* ≡ *a'b' * (mod *n*).
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 *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.

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*. (Because the residue 1 when raised to any power is congruent to 1 modulo *n*, the set of such elements is nonempty.)^{[8]} 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 341 = 11 × 31 is famous since 2^{340} 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.

*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.

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.