the division algorithm
(another Prime Pages' Glossary entries)
The Prime Glossary
Glossary: Prime Pages: Top 5000: 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


Chris K. Caldwell © 1999-2017 (all rights reserved)