↑ arvau

Wikipedia / Multiplicative group of integers modulo n

In modular arithmetic, the integers coprime (relatively prime) to n 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.

, 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 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 . 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. 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 or (the notation refers to taking the quotient of integers modulo the ideal consisting of the multiples of 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 (for German Einheit, which translates as unit

refers to the cyclic group of order n. It is isomorphic to the group of integers modulo n for a prime p, but the isomorphism is not obvious.

Structure

The order of the multiplicative group of integers modulo n coprime to n. It is given by Euler's totient function . For prime p.

Cyclic case

is cyclic if and only if n is 1, 2, 4, pk or 2pk, 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 give all possible residues modulo n coprime to n is called a primitive root modulo n. of them.

Powers of 2

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.

is the trivial group.

the cyclic group with two elements.

the Klein four-group.

is the 2-torsion subgroup

The pattern shown by 8 and 16 holds for higher powers 2k, cannot be cyclic, and the powers of 3 are a cyclic subgroup of order , so:

General composite numbers

By the fundamental theorem of finite abelian groups is isomorphic to a direct product of cyclic groups of prime power orders.

More specifically, the Chinese remainder theorem is the direct product of the rings corresponding to each of its prime power factors:

is the direct product of the groups corresponding to each of the prime power factors:

is not cyclic unless k = 0, 1, 2, but factors into cyclic groups as described above.

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 is the smallest number such that for each a coprime to n and is equal to it if and only if the group is cyclic.

Subgroup of false witnesses

If n, the elements which, raised to the power , are congruent to 1 modulo n. Fermat's Little Theorem states that for n = p; 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 = , and n = 341 is the smallest composite number for which x =.

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

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.

Examples

and a generating set for n ≤ 128. The decomposition and generating sets are not unique; for example,

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

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)

  1. 0, 1, 2, 3, 2, 5, 3, 0, 2, 3, 2, 0, 2, 3, 0, 0, 3, 5, 2, 0, 0, 7, 5, 0, 2, 7, 2, 0, 2, 0, 3, 0, 0, 3, 0, 0, 2, 3, 0, 0, 6, 0, 3, 0, 0, 5, 5, 0, 3, 3, 0, 0, 2, 5, 0, 0, 0, 3, 2, 0, 2, 3, 0, 0, 0, 0, 2, 0, 0, 0, 7, 0, 5, 5, 0, 0, 0, 0, 3, 0, 2, 7, 2, 0, 0, 3, 0, 0, 3, 0, ...

Numbers of the elements in a minimal generating set of mod n are

  1. 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 1, 2, 2, 1, 1, 1, 2, 2, 1, 1, 3, 1, 1, 1, 2, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2, 3, 1, 2, 1, 2, 2, 1, 1, 3, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 1, 1, 2, 2, 2, 2, 1, 2, 2, 2, 1, 3, 1, 1, 2, 2, 2, 2, 1, 3, 1, 1, 1, 3, 2, 1, 2, 3, 1, 2, ...

See also

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.

|+ !k !2 !3 !4 !5 !6 !7 !8 !9 |- |OEIS | | | | | | | | |}