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 06:46, 9 October 2009 edit123.243.212.112 (talk) Added an example to further illustrate the definition.← Previous edit Revision as of 10:44, 23 October 2009 edit undo63.249.90.243 (talk)No edit summaryNext edit →
Line 1: Line 1:
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 ]. 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 ].


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


==Facts== ==Facts==

Revision as of 10:44, 23 October 2009

A reduced residue system modulo n is a set of ϕ {\displaystyle \phi } (n) integers such that each integer is relatively prime to n and no two are congruent modulo n. Here ϕ {\displaystyle \phi } denotes Euler's totient function.

A reduced residue system modulo n is the reduced version of the residue number system 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 { 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 , 11 } {\displaystyle \{0,1,2,3,4,5,6,7,8,9,10,11\}} . 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 { 1 , 5 , 7 , 11 } {\displaystyle \{1,5,7,11\}} .

Facts

  • If { r 1 , r 2 , … , r φ ( n ) } {\displaystyle \{r_{1},r_{2},\dots ,r_{\varphi (n)}\}} is a reduced residue system with n > 2, then ∑ r i ≡ 0 ( mod n ) {\displaystyle \sum r_{i}\equiv 0{\pmod {n}}} .

See also

External links

Stub icon

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

Categories: