Misplaced Pages

Revision as of 03:22, 8 April 2013

Any subset R of the set of 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 not relatively prime to 12, and so the corresponding reduced residue system modulo 12 is {1,5,7,11}. Note that the cardinality of this set is ${\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 {r₁, r₂, ... , r_φ(n)} is a reduced residue system with n > 2, then ${\displaystyle \sum r_{i}\equiv 0{\pmod {n}}}$.
• If n is prime, then every number in a reduced residue system mod n (except for 1) is a generator for the multiplicative group of integers mod n.

See also

• Complete residue system modulo m
• Congruence relation
• Euler's totient function
• Greatest common divisor
• Least residue system modulo m
• Modular arithmetic
• Number theory
• Residue number system

Notes

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

References

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

External links

• Residue systems at PlanetMath
• Reduced residue system at MathWorld

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

• v
• t
• e

• Modular arithmetic
• Elementary number theory
• Number theory stubs