Misplaced Pages

Reduced residue system: Difference between revisions

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.
Browse history interactively← Previous editContent deleted Content addedVisualWikitext
Revision as of 03:42, 15 November 2009 edit123.243.212.112 (talk) added euler's totient function to example← Previous edit Latest revision as of 19:42, 29 April 2024 edit undoR'n'B (talk | contribs)Administrators421,354 editsm Disambiguating links to Group (link changed to Group (mathematics)) using DisamAssist. 
(46 intermediate revisions by 22 users not shown)
Line 1: Line 1:
{{Short description|Set of residue classes modulo n, relatively prime to n}}
A '''reduced residue system''' modulo ''n'' is a set of <math>\phi</math>(''n'') integers such that each integer is relatively prime to ''n'' and no two are congruent modulo ''n''. Here <math>\phi</math> denotes ].
In ], a ] ''R'' of the ] is called a '''reduced residue system modulo''' ''n'' if:


#gcd(''r'', ''n'') = 1 for each ''r'' in ''R'',
⚫ A reduced residue system modulo n is the reduced version of the ] modulo n; where all elements within the residue number system which are not relatively prime to n are removed. For example, the residue number system modulo 12 is <math>\{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11\}</math>. 1, 5, 7 and 11 are the only residues modulo 12 which are relatively prime to 12, and so the reduced residue system modulo 12 is <math>\{1,5,7,11\}</math>. In this case, <math>\phi(12)=4</math>, as Euler's totient function gives the length of the reduced residue system.
#''R'' contains φ(''n'') elements,
#no two elements of ''R'' are ] modulo ''n''.<ref>{{harvtxt|Long|1972|p=85}}</ref><ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=104}}</ref>

Here φ denotes ].

⚫ A reduced residue system modulo ''n'' can be formed from a ] modulo ''n'' by removing all integers not ] 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 ]s 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 ] 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== ==Facts==
*Every number in a reduced residue system modulo ''n'' is a ] for the additive ] of integers modulo ''n''.
⚫ *If <math>\{ r_1, r_2, \dots, r_{\varphi(n)} \}</math> is a reduced residue system with ''n'' > 2, then <math>\sum r_i \equiv 0 \pmod n</math>.
*A reduced residue system modulo ''n'' is a ] under multiplication modulo ''n''.
⚫ *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'', and ''a'' is an integer such that gcd(''a'', ''n'') = 1, then {''ar''<sub>1</sub>, ''ar''<sub>2</sub>, ... , ''ar''<sub>φ(''n'')</sub>} is also a reduced residue system modulo ''n''.<ref>{{harvtxt|Long|1972|p=86}}</ref><ref>{{harvtxt|Pettofrezzo|Byrkit|1970|p=108}}</ref>


==See also== ==See also==
*]
*]
*]
*]
*]
*]
*]
*]
*] *]

== Notes ==
<references/>

== References ==
* {{citation |last=Long |first=Calvin T. |year=1972 |title=Elementary Introduction to Number Theory |edition=2nd |publisher=] |location=Lexington |lccn=77171950}}
* {{citation |last1=Pettofrezzo |first1=Anthony J. |last2=Byrkit |first2=Donald R. |year=1970 |title=Elements of Number Theory |publisher=] |location=Englewood Cliffs |lccn=71081766}}


==External links== ==External links==
* at PlanetMath
* at MathWorld * at MathWorld

{{math-stub}}


] ]
] ]

Latest revision as of 19:42, 29 April 2024

Set of residue classes modulo n, relatively prime to n

In mathematics, a subset R of the integers is called a reduced residue system modulo n if:

  1. gcd(r, n) = 1 for each r in R,
  2. R contains φ(n) elements,
  3. 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

  • 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 {r1, r2, ... , rφ(n)} is a reduced residue system modulo n with n > 2, then ∑ r i ≡ 0 mod n {\displaystyle \sum r_{i}\equiv 0\!\!\!\!\mod 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

Notes

  1. Long (1972, p. 85)
  2. Pettofrezzo & Byrkit (1970, p. 104)
  3. Long (1972, p. 86)
  4. Pettofrezzo & Byrkit (1970, p. 108)

References

External links

Categories: