Reduced residue system explained

In mathematics, a subset R of the integers is called a reduced residue system modulo n if:

1. gcd(r, n) = 1 for each r in R,
2. R contains φ(n) elements,
3. no two elements of R are congruent modulo n.

Here φ denotes Euler's totient function.

A reduced residue system modulo n can be formed from a complete residue system modulo n by removing all integers not relatively prime to n. For example, a complete residue system modulo 12 is . The so-called totatives 1, 5, 7 and 11 are the only integers in this set which are relatively prime to 12, and so the corresponding reduced residue system modulo 12 is . The cardinality of this set can be calculated with the totient function: φ(12) = 4. Some other reduced residue systems modulo 12 are:

Facts

• Every number in a reduced residue system modulo n is a generator for the additive group of integers modulo n.
• A reduced residue system modulo n is a group under multiplication modulo n.
• If is a reduced residue system modulo n with n > 2, then

\sum r _{i} \equiv 0 \mod n .

• If is a reduced residue system modulo n, and a is an integer such that gcd(a, n) = 1, then is also a reduced residue system modulo n.

See also

• Complete residue system modulo m
• Multiplicative group of integers modulo n
• Congruence relation
• Euler's totient function
• Greatest common divisor
• Least residue system modulo m
• Modular arithmetic
• Number theory
• Residue number system

External links

• Residue systems at PlanetMath
• Reduced residue system at MathWorld