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:13, 4 July 2010 editAndriyK (talk | contribs)Extended confirmed users, Pending changes reviewers3,870 editsNo edit summary← Previous edit Revision as of 06:15, 4 July 2010 edit undoAndriyK (talk | contribs)Extended confirmed users, Pending changes reviewers3,870 editsNo 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 ]. 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 ]. 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>. In this case, <math>\phi(12)=4</math>, as Euler's totient function gives the length of the reduced residue system. 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.

Revision as of 06:15, 4 July 2010

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\}} . In this case, ϕ ( 12 ) = 4 {\displaystyle \phi (12)=4} , as Euler's totient function gives the length of the reduced residue system.

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: