# the division algorithm

The division algorithm is not actually an algorithm, but the following theorem which once was "proved" by giving an algorithm explaining how to divide. (Now the proof is usually based on the well ordering principle.)

The Division Algorithm: Ifaandmare any integers withmnot zero, then there are unique integersqandrsuch thata=qm+rwith 0<r< |m|.

For example, if *a* is 36 and *m* is 13, then
*q* = 2 and *r* = 10 (since 36 = 2^{.}13
+ 10). Likewise if *a* is -63 and *m* is 20,
then *q* = -4 and *r* = 17 (since -63 =
-4^{.}20 + 17). Finally, if *a* is 24 and
*m* is -15, then *q* = -1 and *r* = 9 (since
24 = -1^{.}(-15) + 9).

The unique numbers *q* and *r* are called
the **quotient** and **remainder** respectively. The
remainder is also called the least nonnegative residue
modulo *m*. Finally, *a* = *qm*+*r*
implies *a* ≡ *r* (mod *m*), see congruence.

**See Also:** CongruenceClass

Printed from the PrimePages <primes.utm.edu> © Chris Caldwell.