Katana VentraIP

Multiplicative group of integers modulo n

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 , 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[edit]

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 ab (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, aa' and bb' (mod n) implies aba'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.

Notation[edit]

The set of (congruence classes of) integers modulo n with the operations of addition and multiplication is a ring. It is denoted   or    (the notation refers to taking the quotient of integers modulo the ideal or consisting of the multiples of n). Outside of number theory the simpler notation 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)         (for German Einheit, which translates as unit), , or similar notations. This article uses


The notation refers to the cyclic group of order n. It is isomorphic to the group of integers modulo n under addition. Note that or may also refer to the group under addition. For example, the multiplicative group for a prime p is cyclic and hence isomorphic to the additive group , but the isomorphism is not obvious.

Lenstra elliptic curve factorization

(1986), Disquisitiones Arithmeticae (English translation, Second, corrected edition), translated by Clarke, Arthur A., New York: Springer, ISBN 978-0-387-96254-2

Gauss, Carl Friedrich

Gauss, Carl Friedrich (1965), Untersuchungen uber hohere Arithmetik (Disquisitiones Arithemeticae & other papers on number theory) (German translation, Second edition), translated by Maser, H., New York: Chelsea,  978-0-8284-0191-3

ISBN

(1994), Prime Numbers and Computer Methods for Factorization (second edition), Boston: Birkhäuser, ISBN 978-0-8176-3743-9

Riesel, Hans

(2003), "§ VI Primitive roots and indices", Elements of Number Theory, Mineola, NY: Dover Publications, pp. 105–121, ISBN 978-0-486-49530-9

Vinogradov, I. M.

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.

"Primitive Root". MathWorld.

Weisstein, Eric W.

by John Jones

Web-based tool to interactively compute group tables

OEIS

sequence A033948 (Numbers that have a primitive root (the multiplicative group modulo n is cyclic))

sequence A272592 (2 cyclic groups)

OEIS

sequence A272590 (The smallest number m such that the multiplicative group modulo m is the direct product of n cyclic groups)