In mathematical terms, the division algorithm is defined in the following way:
Let a be an integer and b be a natural number. Then there exist unique integers q and r such that a=b*q+r and 0<r<b.
In less formal terms, q is the quotient and r is the remainder. Some examples:
- a=42, b=8; q=5, r=2.
- a=-87, b=20; q=-5, r=13.
- a=404, b=1300; q=0, r=404.
- a=-1, b=10; q=-1, r=9.
The division algorithm is the formal statement of the method of long division, with the allowance made for negativeprimenumbers.
Proof (existence and uniqueness):
Let a be an integer and b be a natural number. Let q be the greatest integer less than or equal to a/b. Then b*q<a. Let r=a-b*q. Then r is positive or zero, and a=b*q+r. Notice that a<b*q+b = b*(q+1), because q was chosen to be the greatest integer less than or equal to a/b. So b*q+r < b*q+b, and r<b. QED (existence)
Let a be an integer and b be a natural number. Let q1 and r1 be integers such that a=b*q1+r1 and 0<r1<b. Further, let q2 and r2 be integers such that a=b*q2+r2 and 0<r2<b. Then b*(q1-q2) = r2-r1, and b divides r2-r1. But, both r1 and r2 are between 0 and b, so -b < r2-r1 < b. These conditions can only be satisfied when r1=r2. This implies that q1=q2. QED (uniqueness)