Any subset R of the integers is called a reduced residue system modulo n if:
- gcd(r, n) = 1 for each r contained in R;
- R contains φ(n) elements;
- no two elements of R are congruent modulo n.
Here
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}. The cardinality of this set can be calculated with the totient function:
Facts
References
Reduced residue system Wikipedia(Text) CC BY-SA