 Multiplicative group of integers modulo n

In modular arithmetic the set of congruence classes relatively prime to the modulus n form a group under multiplication called the multiplicative group of integers modulo n. It is also called 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. (Units refers to elements with a multiplicative inverse.)
This group is fundamental in number theory. It has found applications in cryptography, integer factorization, and primality testing. For example, by finding the order (ie. the size) of the group, one can determine if n is prime: n is prime if and only if the order is n − 1.
Contents
Group axioms
It is a straightforward exercise to show that under multiplication the congruence classes (mod n) which are relatively prime to n satisfy the axioms for an abelian group.
Because a ≡ b (mod n) implies that gcd(a, n) = gcd(b, n), the notion of congruence classes (mod n) which are relatively prime to n is welldefined.
Since gcd(a, n) = 1 and gcd(b, n) = 1 implies gcd(ab, n) = 1 the set of classes relatively prime to n is closed under multiplication.
The natural mapping from the integers to the congruence classes (mod n) that takes an integer to its congruence class (mod n) respects products. This implies that the class containing 1 is the unique multiplicative identity, and also the associative and commutative laws. In fact it is a ring homomorphism.
Given a, gcd(a, n) = 1, finding x satisfying ax ≡ 1 (mod n) is the same as solving ax + ny = 1, which can be done by Bézout's lemma. The x found will have the property that gcd(x,n)=1.
Notation
The ring of integers (mod n) is denoted or (i.e., the ring of integers modulo the ideal nZ = (n) consisting of the multiples of n) or by (though the latter can be confused with the padic integers in the case n = p). Depending on the author its group of units may be written (for German Einheit = unit) or similar notations. This article uses
Structure
Powers of 2
Modulo 2 there is only one relatively prime congruence class, 1, so is trivial.
Modulo 4 there are two relatively prime congruence classes, 1 and 3, so the cyclic group with two elements.
Modulo 8 there are four relatively prime classes, 1, 3, 5 and 7. The square of each of these is 1, so the Klein fourgroup.
Modulo 16 there are eight relatively prime classes 1, 3, 5, 7, 9, 11, 13 and 15. is the 2torsion subgroup (ie. the square of each element is 1), so is not cyclic. The powers of 3, {1,3,9,11} are a subgroup of order 4, as are the powers of 5, {1,5,9,13}. Thus
The pattern shown by 8 and 16 holds^{[1]} for higher powers 2^{k}, k > 2: is the 2torsion subgroup (so is not cyclic) and the powers of 3 are a subgroup of order 2^{k − 2}, so
Powers of odd primes
For powers of odd primes p^{k} the group is cyclic:^{[2]}
General composite numbers
The Chinese remainder theorem^{[3]} 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:
Order
The order of the group is given by Euler's totient function: This is the product of the orders of the cyclic groups in the direct product.
Exponent
The exponent is given by the Carmichael function λ(n), the least common multiple of the orders of the cyclic groups. This means that given n, for any a relatively prime to n, and λ(n) is the smallest such number.
Generators
is cyclic if and only if φ(n) = λ(n). This is the case precisely when n is 2, 4, a power of an odd prime, or twice a power of an odd prime. In this case a generator is called a primitive root modulo n.
Since all the n = 1, 2, ..., 7 are cyclic, another way to state this is: If n < 8 then has a primitive root. If n ≥ 8 has a primitive root unless n is divisible by 4 or by two distinct odd primes.
In the general case there is one generator for each cyclic direct factor.
Table
This table shows the cyclic decomposition of and a generating set for small values of n. The generating sets are not unique; e.g. (mod 16) both {−1, 3} and {−1, 5} will work. The generators are listed in the same order as the direct factors.
For example take n = 20. φ(20) = 8 means that the order of is 8 (i.e. there are 8 numbers less than 20 and coprime to it); λ(20) = 4 that the fourth power of any number relatively prime to 20 is ≡ 1 (mod 20); and as for the generators, 19 has order 2, 3 has order 4, and every member of is of the form 19^{a} × 3^{b}, where a is 0 or 1 and b is 0, 1, 2, or 3.
The powers of 19 are {±1} and the powers of 3 are {3, 9, 7, 1}. The latter and their negatives (mod 20), {17, 11, 13, 19} are all the numbers less than 20 and prime to it. The fact that the order of 19 is 2 and the order of 3 is 4 implies that the fourth power of every member of is ≡ 1 (mod 20).
Group Structure of (Z/nZ)^{×} generating set generating set 2 {1} 1 1 1 33 C_{2}×C_{10} 20 10 10, 2 3 C_{2} 2 2 2 34 C_{16} 16 16 3 4 C_{2} 2 2 3 35 C_{2}×C_{12} 24 12 6, 2 5 C_{4} 4 4 2 36 C_{2}×C_{6} 12 6 19, 5 6 C_{2} 2 2 5 37 C_{36} 36 36 2 7 C_{6} 6 6 3 38 C_{18} 18 18 3 8 C_{2}×C_{2} 4 2 7, 3 39 C_{2}×C_{12} 24 12 38, 2 9 C_{6} 6 6 2 40 C_{2}×C_{2}×C_{4} 16 4 39, 11, 3 10 C_{4} 4 4 3 41 C_{40} 40 40 6 11 C_{10} 10 10 2 42 C_{2}×C_{6} 12 6 13, 5 12 C_{2}×C_{2} 4 2 5, 7 43 C_{42} 42 42 3 13 C_{12} 12 12 2 44 C_{2}×C_{10} 20 10 43, 3 14 C_{6} 6 6 3 45 C_{2}×C_{12} 24 12 44, 2 15 C_{2}×C_{4} 8 4 14, 2 46 C_{22} 22 22 5 16 C_{2}×C_{4} 8 4 15, 3 47 C_{46} 46 46 5 17 C_{16} 16 16 3 48 C_{2}×C_{2}×C_{4} 16 4 47, 7, 5 18 C_{6} 6 6 5 49 C_{42} 42 42 3 19 C_{18} 18 18 2 50 C_{20} 20 20 3 20 C_{2}×C_{4} 8 4 19, 3 51 C_{2}×C_{16} 32 16 50, 5 21 C_{2}×C_{6} 12 6 20, 2 52 C_{2}×C_{12} 24 12 51, 7 22 C_{10} 10 10 7 53 C_{52} 52 52 2 23 C_{22} 22 22 5 54 C_{18} 18 18 5 24 C_{2}×C_{2}×C_{2} 8 2 5, 7, 13 55 C_{2}×C_{20} 40 20 21, 2 25 C_{20} 20 20 2 56 C_{2}×C_{2}×C_{6} 24 6 13, 29, 3 26 C_{12} 12 12 7 57 C_{2}×C_{18} 36 18 20, 2 27 C_{18} 18 18 2 58 C_{28} 28 28 3 28 C_{2}×C_{6} 12 6 13, 3 59 C_{58} 58 58 2 29 C_{28} 28 28 2 60 C_{2}×C_{2}×C_{4} 16 4 11, 19, 7 30 C_{2}×C_{4} 8 4 11, 7 61 C_{60} 60 60 2 31 C_{30} 30 30 3 62 C_{30} 30 30 3 32 C_{2}×C_{8} 16 8 31, 3 63 C_{6}×C_{6} 36 6 2, 5 See also
Lenstra elliptic curve factorization
Notes
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.
 Gauss, Carl Friedrich; Clarke, Arthur A. (translator into English) (1986), Disquisitiones Arithemeticae (Second, corrected edition), New York: Springer, ISBN 0387962549
 Gauss, Carl Friedrich; Maser, H. (translator into German) (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (Second edition), New York: Chelsea, ISBN 0828401918
 Riesel, Hans (1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 0817637435
External links
 Calculator by Shing Hing Man
 Weisstein, Eric W., "Modulo Multiplication Group" from MathWorld.
Categories: Modular arithmetic
 Group theory
 Finite groups
 Multiplication
Wikimedia Foundation. 2010.
Look at other dictionaries:
Multiplicative group — Concepts in group theory category of groups subgroups, normal subgroups group homomorphisms, kernel, image, quotient direct product, direct sum semidirect product, wreath product … Wikipedia
Group (mathematics) — This article covers basic notions. For advanced topics, see Group theory. The possible manipulations of this Rubik s Cube form a group. In mathematics, a group is an algebraic structure consisting of a set together with an operation that combines … Wikipedia
Multiplicative order — In number theory, given an integer a and a positive integer n with gcd(a,n) = 1, the multiplicative order of a modulo n is the smallest positive integer k with ak ≡ 1 (mod n). The order of a modulo n is usually written ordn(a), or On(a). Contents … Wikipedia
Multiplicative inverse — The reciprocal function: y = 1/x. For every x except 0, y represents its multiplicative inverse. In mathematics, a multiplicative inverse or reciprocal for a number x, denoted by 1/x or x−1, is a number which when multiplied by x yields the… … Wikipedia
Primitive root modulo n — In modular arithmetic, a branch of number theory, a primitive root modulo n is any number g with the property that any number coprime to n is congruent to a power of g (mod n ). That is, if g is a primitive root (mod n ) and gcd( a , n ) = 1,… … Wikipedia
Dihedral group — This snowflake has the dihedral symmetry of a regular hexagon. In mathematics, a dihedral group is the group of symmetries of a regular polygon, including both rotations and reflections.[1] Dihedr … Wikipedia
Schnorr group — A Schnorr group is a large prime order subgroup of mathbb{Z}^* p, the multiplicative group of integers modulo p for some prime p. To generate such a group, generate p, q, r such that :p = qr + 1 with p, q prime. Then choose random h in the range… … Wikipedia
Cyclic group — Group theory Group theory … Wikipedia
Orthogonal group — Group theory Group theory … Wikipedia
Abelian group — For other uses, see Abelian (disambiguation). Abelian group is also an archaic name for the symplectic group Concepts in group theory category of groups subgroups, normal subgroups group homomorphisms, kernel, image, quotient direct product,… … Wikipedia