In mathematics, a subset R of the integers is called a reduced residue system modulo n if: gcd(r, n) = 1 for each r in R, R contains φ(n) elements, 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: {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 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.
See also Multiplicative group of integers modulo n Congruence relation Euler's totient function Greatest common divisor Modular arithmetic Number theory Residue number system
Notes
References
External links Residue systems at PlanetMath Reduced residue system at MathWorld