Reduced residue system


In mathematics, a subset R of the integers is called a reduced residue system modulo n if:
  1. gcd = 1 for each r in R,
  2. R contains φ 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: φ = 4. Some other reduced residue systems modulo 12 are:

Facts