| Revision as of 21:15, 8 November 2011 editAnita5192 (talk | contribs)Extended confirmed users, Pending changes reviewers, Rollbackers19,130 edits Added footnotes.← Previous edit | Revision as of 18:31, 11 November 2011 edit undoAnita5192 (talk | contribs)Extended confirmed users, Pending changes reviewers, Rollbackers19,130 edits Inserted links to complete and least residue system modulo m.Next edit → | ||
| Line 7: | Line 7: | ||
| Here <math>\varphi</math> denotes ]. | Here <math>\varphi</math> denotes ]. | ||
| 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}. Note that the ] of this set is <math>\varphi(12) = 4</math>. Some other reduced residue systems modulo 12 are | A reduced residue system modulo ''n'' can be formed from a ] 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}. Note that the ] of this set is <math>\varphi(12) = 4</math>. Some other reduced residue systems modulo 12 are | ||
| *{13,17,19,23} | *{13,17,19,23} | ||
| Line 19: | Line 19: | ||
| ==See also== | ==See also== | ||
| *] | |||
| *] | *] | ||
| *] | *] | ||
| ⚫ | *] | ||
| *] | |||
| *] | *] | ||
| *] | *] | ||
| *] | *] | ||
| ⚫ | *] | ||
| == Notes == | == Notes == | ||
Revision as of 18:31, 11 November 2011
Any subset R of the set of integers is called a reduced residue system modulo n if
- gcd(r, n) = 1 for each r contained in R;
- R contains φ(n) elements;
- no two elements of R are congruent modulo n.
Here denotes Euler's totient function.
denotes 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}. Note that the cardinality of this set is . Some other reduced residue systems modulo 12 are
. 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 .
- 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
- Long (1972, p. 85)
- Pettofrezzo & Byrkit (1970, p. 104)
References
- Long, Calvin T. (1972), Elementary Introduction to Number Theory (2nd ed.), Lexington: D. C. Heath and Company.
- Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Elements of Number Theory, Englewood Cliffs: Prentice Hall.
External links
- Residue systems at PlanetMath
- Reduced residue system at MathWorld
 | This mathematics-related article is a stub. You can help Misplaced Pages by expanding it. |