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 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:. 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, then.
  • If is a reduced residue system modulo n, and a is an integer such that, then is also a reduced residue system modulo n.