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

gcd(r, n) = 1 for each r in R,
R contains φ(n) elements,
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 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}. 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 {1, 5, 7, 11}. The cardinality of this set can be calculated with the totient function: φ(12) = 4. Some other reduced residue systems modulo 12 are:

{13,17,19,23}
{−11,−7,−5,−1}
{−7,−13,13,31}
{35,43,53,61}

Facts
If {r1, r2, ... , rφ(n)} is a reduced residue system modulo n with n > 2, then . Every number in a reduced residue system modulo n is a generator for the additive group of integers modulo n.
If {r1, r2, ... , rφ(n)} is a reduced residue system modulo n, and a is an integer such that gcd(a, n) = 1, then {ar1, ar2, ... , arφ(n)} 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

Notes

References

External links
Residue systems at PlanetMath
Reduced residue system at MathWorld

Modular arithmetic
Elementary number theory