Misplaced Pages

Reduced residue system

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.

This is an old revision of this page, as edited by WilliamJennings1989 (talk | contribs) at 06:56, 4 April 2016 (The references describe the proof and should then be attributed to the punctuation mark which lists the conditions which must be true if the definition is used.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

Revision as of 06:56, 4 April 2016 by WilliamJennings1989 (talk | contribs) (The references describe the proof and should then be attributed to the punctuation mark which lists the conditions which must be true if the definition is used.)(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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.

Here φ {\displaystyle \varphi } 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}. 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 {\displaystyle \varphi (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 with n > 2, then r i 0 ( mod n ) {\displaystyle \sum r_{i}\equiv 0{\pmod {n}}} .
  • Every number in a reduced residue system mod n is a generator for the additive group of integers modulo n.

See also

Notes

  1. Long (1972, p. 85)
  2. Pettofrezzo & Byrkit (1970, p. 104)

References

External links

Stub icon

This number theory-related article is a stub. You can help Misplaced Pages by expanding it.

Categories: