## You are here

Homeresidue systems

## Primary tabs

# 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\;\;(\mathop{{\rm mod}}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).

## Mathematics Subject Classification

11-00*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections