|
the division algorithm (another Prime Pages' Glossary entries) |
|
|
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 Caldwell © 1999-2010 (all rights reserved)
|