Login
Login

reduced residue system

{{Short description|Set of residue classes modulo n, relatively prime to n}}

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.{{harvtxt|Long|1972|p=85}}{{harvtxt|Pettofrezzo|Byrkit|1970|p=104}}

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

  • 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 {r1, r2, ... , rφ(n)} is a reduced residue system modulo n with n > 2, then \sum r_i \equiv 0\!\!\!\!\mod 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.{{harvtxt|Long|1972|p=86}}{{harvtxt|Pettofrezzo|Byrkit|1970|p=108}}

See also

Notes

References

  • {{citation |last=Long |first=Calvin T. |year=1972 |title=Elementary Introduction to Number Theory |edition=2nd |publisher=D. C. Heath and Company |location=Lexington |lccn=77171950}}
  • {{citation |last1=Pettofrezzo |first1=Anthony J. |last2=Byrkit |first2=Donald R. |year=1970 |title=Elements of Number Theory |publisher=Prentice Hall |location=Englewood Cliffs |lccn=71081766}}

External links

  • [http://planetmath.org/ResidueSystems Residue systems] at PlanetMath
  • [http://mathworld.wolfram.com/ReducedResidueSystem.html Reduced residue system] at MathWorld

Category:Modular arithmetic

Category:Elementary number theory