Misplaced Pages

Revision as of 07:17, 8 November 2010

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

(i) (r, n) = 1 for each r contained in R;

(ii) R contains ${\displaystyle \varphi }$(n) elements;

(iii) 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 ${\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 ${\displaystyle \{r_{1},r_{2},\dots ,r_{\varphi (n)}\}}$ is a reduced residue system with n > 2, then ${\displaystyle \sum r_{i}\equiv 0{\pmod {n}}}$.

See also

• Congruence relation
• Euler's totient function
• Modular arithmetic
• Number theory
• Residue number system

External links

• Reduced residue system at MathWorld

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

• v
• t
• e

• Mathematics stubs
• Modular arithmetic
• Elementary number theory