Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Multiplicative group of integers modulo n
Summary
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 quotient 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.
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.
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.