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_1a,\,k_2a,\,\ldots,\,k_{\varphi(a)}a$$ form a reduced residue system modulo $m$ .

Bibliography

1

K. V¨AISÄLÄ: Lukuteorian ja korkeamman algebran alkeet. Otava, Helsinki (1950).