In modular arithmetic, the integers coprime (relatively prime) to n from the set { 0 , 1 , … , n − 1 } {\displaystyle \{0,1,\dots ,n-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 ( Z / n Z ) × {\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }} , is fundamental in number theory. 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: | ( Z / n Z ) × | = φ ( n ) . {\displaystyle |(\mathbb {Z} /n\mathbb {Z} )^{\times }|=\varphi (n).} For prime n the group is cyclic, and in general the structure is easy to describe, but no simple 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 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. An example for calculating x can be found in the article Modular multiplicative inverse.
Notation The set of (congruence classes of) integers modulo n with the operations of addition and multiplication is a ring. It is denoted Z / n Z {\displaystyle \mathbb {Z} /n\mathbb {Z} } or Z / ( n ) {\displaystyle \mathbb {Z} /(n)} (the notation refers to taking the quotient of integers modulo the ideal n Z {\displaystyle n\mathbb {Z} } or ( n ) {\displaystyle (n)} consisting of the multiples of n). Outside of number theory the simpler notation Z n {\displaystyle \mathbb {Z} _{n}} is often used, though it can be confused with the p-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) ( Z / n Z ) × , {\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times },} ( Z / n Z ) ∗ , {\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{*},} U ( Z / n Z ) , {\displaystyle \mathrm {U} (\mathbb {Z} /n\mathbb {Z} ),} E ( Z / n Z ) {\displaystyle \mathrm {E} (\mathbb {Z} /n\mathbb {Z} )} (for German Einheit, which translates as unit), Z n ∗ {\displaystyle \mathbb {Z} _{n}^{*}} , or similar notations. This article uses ( Z / n Z ) × . {\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }.}
… excerpt ends here. Continue reading the full article.
