Multiplicative group of integers modulo n

The residue class group is the group of prime residue classes with respect to a module. It is listed as or. The prime residue classes are exactly the multiplicative invertible residue classes. The prime residue class groups are therefore finite abelian group with respect to multiplication. They play an important role in cryptography.

The group consists of the residue classes whose elements are relatively prime. Equivalent to have to apply to the representative of the residue class, where gcd denotes the greatest common divisor. Then, the term " residue class " out of prime, one also says relatively prime. The group order of is given by the value of Euler's φ function.

The combination of two primers cosets is induced by multiplying the elements of the remaining classes.

In the language of ring theory, the residue class group is the group of invertible elements in the multiplicative semigroup of the residue class ring.

Structure

Refers to the evaluation of ( the multiplicity of the prime factor in ), so it is

The prime factorization of, then:

The first Isomorphieaussage ( decomposition of the module into its prime factors ) follows from the Chinese remainder theorem. The second Isomorphieaussage ( structure of the reduced residue class group modulo prime power ) follows from the existence of certain primitive roots (see also the corresponding main articles primitive root ).

Note: With the groups without the additive groups etc. are meant!

Is exactly then cyclically if the same or an odd prime and a positive integer. Just then, there are also primitive roots modulo, ie integers whose residue class is a generator of.

Calculation of the inverse elements

For every prime residue class exists a residue class, so that:

The residue class group is thus the inverse element with respect to multiplication in the prime residue class group. A representative from can be determined with the help of the extended Euclidean algorithm. The algorithm is applied to and and provides integers and satisfy the following equation:

It follows. is therefore a representative of the multiplicative inverse to residue class.