the division algorithm (another Prime Pages' Glossary entries) Glossary: Prime Pages: Top 5000: GIMPS has discovered a new largest known prime number: 282589933-1 (24,862,048 digits)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-2019 (all rights reserved)