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 editNext edit →Content deleted Content addedVisualWikitext
Revision as of 21:42, 21 June 2021 editAnita5192 (talk | contribs)Extended confirmed users, Pending changes reviewers, Rollbackers19,128 edits →Facts: Fixed several mistakes in the previous edit. I assume this is what you meant. Otherwise, you will need to cite a source to include it.← Previous edit Revision as of 17:28, 2 November 2021 edit undoCewbot (talk | contribs)Bots7,777,830 editsm Fix broken anchor: 2020-04-23 #Definition of congruence relation→Modular arithmetic#CongruenceNext edit →
Line 4: Line 4:
#gcd(''r'', ''n'') = 1 for each ''r'' in ''R'', #gcd(''r'', ''n'') = 1 for each ''r'' in ''R'',
#''R'' contains φ(''n'') elements, #''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> #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 ]. Here φ denotes ].

Revision as of 17:28, 2 November 2021

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

  • 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} .
  • 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

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: