Residue systems

This article page is a stub, please help by expanding it.

A subset $\scriptstyle R\,$ of the set of integers is called a residue system modulo $\scriptstyle n\,$ if no two elements of $\scriptstyle R\,$ are congruent modulo $\scriptstyle n\,$.

For example, a residue system modulo 12 is {12, 13, 14, 15, 22, 23}, which is equivalent to {0, 1, 2, 3, 10, 11}.

Complete residue systems

A subset $\scriptstyle R\,$ of the set of integers is called a complete residue system modulo $\scriptstyle n\,$ if

• no two elements of $\scriptstyle R\,$ are congruent modulo $\scriptstyle n\,$,
• $\scriptstyle R\,$ contains $\scriptstyle n\,$ elements.

For example, a complete residue system modulo 12 is {12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23}, which is equivalent to {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}.

Reduced residue systems

A subset $\scriptstyle R\,$ of the set of integers is called a reduced residue system modulo $\scriptstyle n\,$ if

• no two elements of $\scriptstyle R\,$ are congruent modulo $\scriptstyle n\,$,
• $\scriptstyle \gcd(r,\,n)\,=\,1\,$ for each $\scriptstyle r\,\in \,R\,$,
• $\scriptstyle R\,$ contains $\scriptstyle \varphi (n)\,$ elements,

where $\scriptstyle \varphi (n)\,$ denotes Euler's totient function.

A reduced residue system modulo $\scriptstyle n\,$ can be formed from a complete residue system modulo $\scriptstyle n\,$ by removing all integers not relatively prime to $\scriptstyle 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 $\scriptstyle \varphi (12)\,=\,4\,$. Some other reduced residue systems modulo 12 are {13, 17, 19, 23} and {−11, −7, −5, −1}.

Totatives

A reduced residue system modulo $\scriptstyle n\,$ where all residues are in $\scriptstyle [0,\,\ldots ,\,n-1]\,$ is called the set of totatives of $\scriptstyle n\,$.

A051250 Numbers whose reduced residue system consists of 1 and prime powers only. (Conjecture: the sequence is finite and 60 is the largest term, empirically verified up to 10^7.)

{1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 14, 18, 20, 24, 30, 42, 60, ?}