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: If a and m are any integers with m not zero, then there are unique integers q and r such that a = qm+r with 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