Reduced residue system Information & Reduced residue system Links at HealthHaven.com

A reduced residue system modulo n is a set of $φ$ (n) integers such that each integer is relatively prime to n and no two are congruent modulo n. Here $φ$ 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 ${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 ${1,5,7,11}$ . In this case, $φ(12) = 4$ , as Euler's totient function gives the length of the reduced residue system.

[edit] Facts

If $\{ r_1, r_2, \dots, r_{\varphi(n)} \}$ is a reduced residue system with n > 2, then $\sum r_i \equiv 0 \pmod n$ .

[edit] See also

Residue number system

[edit] External links

Reduced residue system at MathWorld

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