Reduced residue system

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Any subset R of the integers is called a reduced residue system modulo n if:

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

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: . 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[edit]

  • If {r1, r2, ... , rφ(n)} is a reduced residue system with n > 2, then .
  • Every number in a reduced residue system mod n is a generator for the additive group of integers modulo n.

See also[edit]

Notes[edit]

References[edit]

  • Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company, LCCN 77171950
  • Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall, LCCN 71081766

External links[edit]