residue systems

Definition.  Let $m$ be a positive integer.  A complete residue system modulo $m$ is a set  $\{a_0,a_1,\mathrm{\dots },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,\mathrm{\hspace{0.17em}1},\mathrm{\dots },m-1$,  they satisfy   $a_{\nu }\equiv \nu (modm)$.

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

$$0,\mathrm{\hspace{0.17em}1},\mathrm{\dots },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},\mathrm{\dots },-2,-1,\mathrm{\hspace{0.17em}0},\mathrm{\hspace{0.17em}1},\mathrm{\hspace{0.17em}2},\mathrm{\dots },\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,\mathrm{\hspace{0.17em}1}a+b,\mathrm{\hspace{0.17em}2}a+b,\mathrm{\dots },(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 $\phi (m)$ integers, where $\phi$ 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 $\phi (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,\mathrm{\dots },k_{\phi (m)}\}$  is a reduced residue system modulo $m$, then also the numbers

$$k_{1}a,k_{2}a,\mathrm{\dots },k_{\phi (a)}a$$

form a reduced residue system modulo $m$.

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