info prev up next book cdrom email home

Residue Class

The residue classes of a function $f(x)$ mod $n$ are all possible values of the Residue $f(x){\rm\ (mod\ }n)$. For example, the residue classes of $x^2$ (mod 6) are $\{0, 1, 3, 4\}$, since
$ 0^2\equiv 0\ \left({{\rm mod\ } {6}}\right)$
$ 1^2\equiv 1\ \left({{\rm mod\ } {6}}\right)$
$ 2^2\equiv 4\ \left({{\rm mod\ } {6}}\right)$
$ 3^2\equiv 3\ \left({{\rm mod\ } {6}}\right)$
$ 4^2\equiv 4\ \left({{\rm mod\ } {6}}\right)$
$ 5^2\equiv 3\ \left({{\rm mod\ } {6}}\right)$
are all the possible residues. A Complete Residue System is a set of integers containing one element from each class, so in this case, $\{0, 1, 9, 16\}$ would be a Complete Residue System for $x^2$ (mod 6), as would $\{0, 5,
3, 4\}$, etc.

The $\phi(m)$ residue classes prime to $m$ form a Group under the binary multiplication operation (mod $m$), where $\phi(m)$ is the Totient Function (Shanks 1993) and the Group is classed a Modulo Multiplication Group.

See also Complete Residue System, Congruence, Cubic Number, Quadratic Reciprocity Theorem, Quadratic Residue, Residue (Congruence), Square Number


Shanks, D. Solved and Unsolved Problems in Number Theory, 4th ed. New York: Chelsea, p. 56 and 59-63, 1993.

© 1996-9 Eric W. Weisstein