Misplaced Pages

This is an old revision of this page, as edited by AndriyK (talk | contribs) at 06:13, 4 July 2010. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

A reduced residue system modulo n is a set of ${\displaystyle \phi }$(n) integers such that each integer is relatively prime to n and no two are Modular_arithmetic#The_congruence_relation. Here ${\displaystyle \phi }$ denotes Euler's totient function.

A reduced residue system modulo n is the reduced version of the residue number system modulo n; where all elements within the residue number system which are not relatively prime to n are removed. For example, the residue number system modulo 12 is ${\displaystyle \{0,1,2,3,4,5,6,7,8,9,10,11\}}$. 1, 5, 7 and 11 are the only residues modulo 12 which are relatively prime to 12, and so the reduced residue system modulo 12 is ${\displaystyle \{1,5,7,11\}}$. In this case, ${\displaystyle \phi (12)=4}$, as Euler's totient function gives the length of the reduced residue system.

Facts

• If ${\displaystyle \{r_{1},r_{2},\dots ,r_{\varphi (n)}\}}$ is a reduced residue system with n > 2, then ${\displaystyle \sum r_{i}\equiv 0{\pmod {n}}}$.

See also

• Residue number system

External links

• Reduced residue system at MathWorld

This mathematics-related article is a stub. You can help Misplaced Pages by expanding it.

• v
• t
• e

• Mathematics stubs
• Modular arithmetic
• Elementary number theory