1911 Encyclopædia Britannica/Number/Residues and congruences

27. Residues and congruences.—It will now be convenient to include in the term “number” both zero and negative integers. Two numbers $a,b$ are said to be congruent with respect to the modulus $m$, when $(a-b)$ is divisible by $m$. This is expressed by the notation $a\equiv b{\pmod {m}}$, which was invented by Gauss. The fundamental theorems relating to congruences are

If $a\equiv b$ and $c\equiv d{\pmod {m}}$, then $a\pm c\equiv b\pm d$, and $ac\equiv bd$.

If $ha\equiv hb{\pmod {m}}$ then $a\equiv b{\pmod {m/d}}$, where $d=\operatorname {dv} (h,m)$.

Thus the theory of congruences is very nearly, but not quite, similar to that of algebraic equations. With respect to a given modulus $m$ the scale of relative integers may be distributed into $m$ classes, any two elements of each class being congruent with respect to $m$. Among these will be $\phi (m)$ classes containing numbers prime to $m$. By taking any one number from each class we obtain a complete system of residues to the modulus $m$. Supposing (as we shall always do) that $m$ is positive, the numbers $0,1,2,\dots (m-1)$ form a system of least positive residues; according as m is odd or even, $0,\pm 1,\pm 2,\dots \pm {\tfrac {1}{2}}(m-1)$, or $0,\pm 1,\pm 2,\dots \pm {\tfrac {1}{2}}(m-2),{\tfrac {1}{2}}m$ form a system of absolutely least residues.