Prime residual class group

The prime remainder class group is the group of the prime remainder classes with respect to a module . It is noted as or . The prime remainder classes are exactly the multiplicatively invertible elements in the remainder class ring . The prime residue class groups are therefore finite Abelian groups with respect to multiplication . They play an important role in cryptography . ${\displaystyle n}$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$ ${\displaystyle \mathbb {Z} _{n}^{*}}$

The group consists of the remainder classes whose elements are too coprime . Equivalent to this must apply to the representative of the remainder of the class , where gcd denotes the greatest common factor. This is indicated by the designation “ prime residual class”, for coprime one also says relatively prime . The group order of is given by the value of Euler's φ-function . ${\displaystyle a+n\mathbb {Z} }$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle \operatorname {ggT} (a,n)=1}$ ${\displaystyle \mathbb {Z} _{n}^{*}}$ ${\displaystyle \varphi (n)}$

structure

Denotes the - evaluation of (the multiplicity of the prime factor in ), is therefore ${\displaystyle v_{p}}$ ${\displaystyle p}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle n}$

${\displaystyle n=\prod _{p}p^{v_{p}}}$

the prime factorization of , then: ${\displaystyle n}$

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }\cong \prod _{p}(\mathbb {Z} /p^{v_{p}}\mathbb {Z} )^{\times }}$

${\displaystyle {}\cong {\begin{cases}\mathbb {Z} /2\mathbb {Z} \;\times \;\mathbb {Z} /2^{v_{2}-2}\mathbb {Z} \;\times \;\prod _{p\neq 2}\mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} &\mathrm {falls} \ 8\mid n\\\prod _{p}\mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} &\mathrm {sonst} .\end{cases}}}$

or expressed using and the notation for a cyclic group: ${\displaystyle \varphi }$ ${\displaystyle C_{n}}$

${\displaystyle {}\cong {\begin{cases}C_{2}\;\times \;C_{2^{v_{2}-2}}\;\times \;\prod _{p\neq 2}C_{\varphi (p^{v_{p}})}&\mathrm {falls} \ 8\mid n\\\prod _{p}C_{\varphi (p^{v_{p}})}&\mathrm {sonst} .\end{cases}}}$

The first isomorphism statement (decomposition of the module into its prime factors) follows from the Chinese remainder of the law . The second isomorphism statement (structure of the prime residue class group modulo prime power) follows from the existence of certain primitive roots (see also the main article Primitive Root ). ${\displaystyle n}$

Note: The groups without a superscript refer to the additive groups etc.! ${\displaystyle \times }$ ${\displaystyle \mathbb {Z} /(p-1)p^{v_{p}-1}\mathbb {Z} }$

${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$is cyclic if and only if is equal to or has an odd prime number and a positive integer . Exactly then there also exist primitive roots modulo , i.e. integers whose remainder class is a producer of . ${\displaystyle n}$ ${\displaystyle 1,2,4,p^{r}}$ ${\displaystyle 2p^{r}}$ ${\displaystyle p}$ ${\displaystyle r}$ ${\displaystyle n}$ ${\displaystyle a}$ ${\displaystyle a+n\mathbb {Z} }$ ${\displaystyle (\mathbb {Z} /n\mathbb {Z} )^{\times }}$

Calculation of the inverse elements

For every prime remainder class there is a prime remainder class , so that: ${\displaystyle a+n\mathbb {Z} }$ ${\displaystyle b+n\mathbb {Z} }$

${\displaystyle ab\equiv 1{\pmod {n}}}$

The prime remainder class is therefore the inverse element of the multiplication in the prime remainder class group . A representative of can be determined with the help of the extended Euclidean algorithm . The algorithm is on and applied and delivers integers and , satisfy the following equation: ${\displaystyle b+n\mathbb {Z} }$ ${\displaystyle a+n\mathbb {Z} }$ ${\displaystyle \mathbb {Z} _{n}^{*}}$ ${\displaystyle b+n\mathbb {Z} }$ ${\displaystyle a}$ ${\displaystyle n}$ ${\displaystyle s}$ ${\displaystyle t}$

${\displaystyle \operatorname {ggT} (a,n)=1=s\cdot a+t\cdot n}$.

It follows from this , that is, is a representative of the residual class which is inverse to multiplicative . ${\displaystyle 1\equiv sa{\pmod {n}}}$ ${\displaystyle s}$ ${\displaystyle a+n\mathbb {Z} }$ ${\displaystyle b+n\mathbb {Z} }$

literature

The Disquisitiones Arithmeticae were published in Latin by Carl Friedrich Gauß . The contemporary German translation includes all of his writings on number theory:

• Carl Friedrich Gauß : Investigations into higher arithmetic (German translation), Original: Leipzig 1801.

• Armin Leutbecher: Number Theory - An Introduction to Algebra . 1st edition. Springer Verlag, 1996, Berlin Heidelberg New York. ISBN 3-540-58791-8 .

Individual evidence

1. ↑ A. Leutbecher: Number Theory - An Introduction to Algebra , pp. 53–54.