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

$$37 \equiv 3$$

$$37^2 \equiv 3^2\equiv 9\equiv -8$$

$$37^4 \equiv 81\equiv -4$$

$$37^8 \equiv 16\equiv -1,$$

so

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

See also Common Residue, Congruence, Minimal Residue

References

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