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 22:01, 15 May 2011 editJay Gatsby (talk | contribs)Extended confirmed users1,702 editsm These are commonly known facts in number theory. The reference is any elementary number theory textbook.← Previous edit Revision as of 08:47, 19 October 2011 edit undoQuondum (talk | contribs)Extended confirmed users36,993 edits Changed (,) to less cryptic notation gcd(,); removed an unnecessary inline PNG conversion; added see alsoNext edit →
Line 1: Line 1:
Any subset ''R'' of the set of integers is called a '''reduced residue system''' modulo ''n'' if Any subset ''R'' of the set of integers is called a '''reduced residue system''' modulo ''n'' if


#(''r, n'') = 1 for each ''r'' contained in ''R''; #gcd(''r'', ''n'') = 1 for each ''r'' contained in ''R'';
#''R'' contains <math>\varphi</math>(''n'') elements; #''R'' contains φ(''n'') elements;
#no two elements of ''R'' are congruent modulo ''n''. #no two elements of ''R'' are congruent modulo ''n''.


Line 10: Line 10:


*{13,17,19,23} *{13,17,19,23}
*{-11,-7,-5,-1} *{−11,−7,−5,−1}
*{-7,-13,13,31} *{−7,−13,13,31}
*{35,43,53,61} *{35,43,53,61}


==Facts== ==Facts==
*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>. *If {{math|{''r''<sub>1</sub>, ''r''<sub>2</sub>, ... , ''r''<sub>φ(''n'')</sub>} }} is a reduced residue system with ''n'' > 2, then <math>\sum r_i \equiv 0 \pmod n</math>.
*Every number in a reduced residue system mod ''n'' (except for 1) is a generator for the ]. *Every number in a reduced residue system mod ''n'' (except for 1) is a generator for the ].


Line 24: Line 24:
*] *]
*] *]
*]


==External links== ==External links==

Revision as of 08:47, 19 October 2011

Any subset R of the set of integers is called a reduced residue system modulo n if

  1. gcd(r, n) = 1 for each r contained in R;
  2. R contains φ(n) elements;
  3. no two elements of R are congruent modulo n.

Here φ {\displaystyle \varphi } 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}. 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 φ ( 12 ) = 4 {\displaystyle \varphi (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 with n > 2, then ∑ r i ≡ 0 ( mod n ) {\displaystyle \sum r_{i}\equiv 0{\pmod {n}}} .
  • 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

External links

Stub icon

This mathematics-related article is a stub. You can help Misplaced Pages by expanding it.

Categories: