info prev up next book cdrom email home

Residue (Congruence)

The number $b$ in the Congruence $a\equiv b\ \left({{\rm mod\ } {m}}\right)$ is called the residue of $a$ (mod $m$). The residue of large numbers can be computed quickly using Congruences. For example, to find $37^{13}$ (mod 17), note that

$\displaystyle 37$ $\textstyle \equiv$ $\displaystyle 3$  
$\displaystyle 37^2$ $\textstyle \equiv$ $\displaystyle 3^2\equiv 9\equiv -8$  
$\displaystyle 37^4$ $\textstyle \equiv$ $\displaystyle 81\equiv -4$  
$\displaystyle 37^8$ $\textstyle \equiv$ $\displaystyle 16\equiv -1,$  


37^{13}\equiv 37^{1+4+8} \equiv 3(-4)(-1)\equiv 12 {\rm\ (mod\ } 17).

See also Common Residue, Congruence, Minimal Residue


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

© 1996-9 Eric W. Weisstein