# residue systems

Definition.  Let $m$ be a positive integer.  A complete residue system modulo $m$ is a set  $\{a_{0},\,a_{1},\,\ldots,\,a_{m-1}\}$  of integers containing one and only one representant from every residue class modulo $m$.  Thus the numbers $a_{\nu}$ may be ordered such that for all $\nu=0,\,1,\,\ldots,\,m\!-\!1$,  they satisfy   $a_{\nu}\equiv\nu\pmod{m}$.

The least nonnegative remainders modulo $m$, i.e. the numbers

 $0,\,1,\,\ldots,\,m\!-\!1$

form a complete residue system modulo $m$ (see long division).  If $m$ is odd, then also the absolutely least remainders

 $-\frac{m\!-\!1}{2},\,-\frac{m\!-\!3}{2},\,\ldots,\,-2,\,-1,\,0,\,1,\,2,\,% \ldots,\,\frac{m\!-\!3}{2},\,\frac{m\!-\!1}{2}$

offer a complete residue system modulo $m$.

Theorem 1.  If  $\gcd(a,\,m)=1$  and $b$ is an arbitrary integer, then the numbers

 $0a\!+\!b,\,1a\!+\!b,\,2a\!+\!b,\,\ldots,\,(m\!-\!1)a\!+\!b$

form a complete residue system modulo $m$.

One may speak also of a reduced residue system modulo $m$, which contains only one representant from each prime residue class modulo $m$.  Such a system consists of $\varphi(m)$ integers, where $\varphi$ means the Euler’s totient function.

Remark.  A set of integers forms a reduced residue system modulo $m$ if and only if
$1^{\circ}$ it contains $\varphi(m)$ numbers,
$2^{\circ}$ its numbers are coprime with $m$,
$3^{\circ}$ its numbers are incongruent modulo $m$.

Theorem 2.  If  $\gcd(a,\,m)=1$  and  $\{k_{1},\,k_{2},\,\ldots,\,k_{\varphi(m)}\}$  is a reduced residue system modulo $m$, then also the numbers

 $k_{1}a,\,k_{2}a,\,\ldots,\,k_{\varphi(a)}a$

form a reduced residue system modulo $m$.

## References

• 1 K. Väisälä: Lukuteorian ja korkeamman algebran alkeet.  Otava, Helsinki (1950).
 Title residue systems Canonical name ResidueSystems Date of creation 2013-03-22 16:57:08 Last modified on 2013-03-22 16:57:08 Owner pahio (2872) Last modified by pahio (2872) Numerical id 12 Author pahio (2872) Entry type Definition Classification msc 11-00 Related topic PrimeResidueClass Related topic Totative Related topic MathbbZ_n Defines complete residue system Defines reduced residue system Defines least nonnegative remainder Defines absolutely least remainder