Reduced residue system

In mathematics, a

subset

''R'' of the

integers

is called a reduced residue system modulo ''n'' if:

#gcd(''r'', ''n'') = 1 for each ''r'' in ''R'',
#''R'' contains φ(''n'') elements,
#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 . 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 . The cardinality of this set can be calculated with the totient function: φ(12) = 4. Some other reduced residue systems modulo 12 are:

*
*
*
*

Facts

*If is a reduced residue system modulo ''n'' with ''n'' > 2, then $\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 is a reduced residue system modulo ''n'', and ''a'' is an integer such that gcd(''a'', ''n'') = 1, then is also a reduced residue system modulo ''n''.

See also

* Complete residue system modulo m
*Congruence relation
*Euler's totient function
*

Greatest common divisor

* Least residue system modulo m
*Modular arithmetic
*

Number theory

* Residue number system

Notes

References

*
* {{citation , last1=Pettofrezzo , first1=Anthony J. , last2=Byrkit , first2=Donald R. , year=1970 , title=Elements of Number Theory , publisher=Prentice Hall , location=Englewood Cliffs , lccn=71081766

External links

Residue systems
at PlanetMath

at MathWorld

Modular arithmetic
Elementary number theory