mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, a

subset In mathematics, a Set (mathematics), set ''A'' is a subset of a set ''B'' if all Element (mathematics), elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they a ...

''R'' of the

integers An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

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 In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...

. A reduced residue system modulo ''n'' can be formed from a complete residue system modulo ''n'' by removing all integers not

relatively prime In number theory, two integers and are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides does not divide , and vice versa. This is equiv ...

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 The thumb is the first digit of the hand, next to the index finger. When a person is standing in the medical anatomical position (where the palm is facing to the front), the thumb is the outermost digit. The Medical Latin English noun for thum ...

of this set can be calculated with the totient function: φ(12) = 4. Some other reduced residue systems modulo 12 are: * * * *

Facts

*Every number in a reduced residue system modulo ''n'' is a generator for the additive group of integers modulo ''n''. *A reduced residue system modulo ''n'' is a group under multiplication modulo ''n''. *If is a reduced residue system modulo ''n'' with ''n'' > 2, then

\sum r_i \equiv 0\!\!\!\!\mod 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''.

Notes

References

* * {{citation , last1=Pettofrezzo , first1=Anthony J. , last2=Byrkit , first2=Donald R. , year=1970 , title=Elements of Number Theory , publisher=

Prentice Hall Prentice Hall was a major American publishing#Textbook_publishing, educational publisher. It published print and digital content for the 6–12 and higher-education market. It was an independent company throughout the bulk of the twentieth cen ...

, location=Englewood Cliffs , lccn=71081766

External links

Residue systems
at PlanetMath

at MathWorld Modular arithmetic Elementary number theory

Facts

See also

Notes

References

External links