| Revision as of 10:24, 4 March 2022 edit79.18.49.231 (talk)No edit summaryTags: Mobile edit Mobile app edit iOS app edit← Previous edit | Revision as of 17:50, 1 March 2024 edit undo31.111.93.172 (talk) To add to the page explicit statement of this basic propertyTag: Disambiguation links addedNext edit → | ||
| Line 16: | Line 16: | ||
| ==Facts== | ==Facts== | ||
| *A reduced residue system modulo ''n'' is a ] under (modulo ''n'') multiplication | |||
| *If {''r''<sub>1</sub>, ''r''<sub>2</sub>, ... , ''r''<sub>φ(''n'')</sub>} is a reduced residue system modulo ''n'' with ''n'' > 2, then <math>\sum r_i \equiv 0\!\!\!\!\mod n</math>. | *If {''r''<sub>1</sub>, ''r''<sub>2</sub>, ... , ''r''<sub>φ(''n'')</sub>} is a reduced residue system modulo ''n'' with ''n'' > 2, then <math>\sum r_i \equiv 0\!\!\!\!\mod n</math>. | ||
| *Every number in a reduced residue system modulo ''n'' is a ] for the additive ] of integers modulo ''n''. | *Every number in a reduced residue system modulo ''n'' is a ] for the additive ] of integers modulo ''n''. | ||
Revision as of 17:50, 1 March 2024
Set of residue classes modulo n, relatively prime to nIn 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 {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
- A reduced residue system modulo n is a group under (modulo n) multiplication
- If {r1, r2, ... , rφ(n)} is a reduced residue system modulo n with n > 2, then .
- Every number in a reduced residue system modulo n is a generator for the additive group of integers modulo 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.
.See also
- Complete residue system modulo m
- Multiplicative group of integers modulo n
- Congruence relation
- Euler's totient function
- Greatest common divisor
- Least residue system modulo m
- Modular arithmetic
- Number theory
- Residue number system
Notes
- Long (1972, p. 85)
- Pettofrezzo & Byrkit (1970, p. 104)
- Long (1972, p. 86)
- Pettofrezzo & Byrkit (1970, p. 108)
References
- 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
- Residue systems at PlanetMath
- Reduced residue system at MathWorld