division algorithm for integers


Given any two integers a,b where b>0, there exists a unique pair of integers q,r such that a=qb+r and 0r<b. q is called the quotient of a and b, and r is the remainder.

The division algorithm is not an algorithm at all but rather a theorem. Its name probably derives from the fact that it was first proved by showing that an algorithm to calculate the quotient of two integers yields this result.

There are similar forms of the division algorithm that apply to other rings (for example, polynomialsPlanetmathPlanetmath).

Title division algorithm for integers
Canonical name DivisionAlgorithmForIntegers
Date of creation 2013-03-22 11:59:43
Last modified on 2013-03-22 11:59:43
Owner vampyr (22)
Last modified by vampyr (22)
Numerical id 7
Author vampyr (22)
Entry type Theorem
Classification msc 11A51
Synonym division algorithm
Related topic ExistenceAndUniquenessOfTheGcdOfTwoIntegers