Integer division: revisited and new

When you divide an integer by another, and if you are not interested in fractions, you will get a quotient and remainder. You know this already. Let us make this more precise. The usual mathematical way to express the idea of division with remainder is not to talk about the division itself, but about reconstructing the dividend from the quotient, divisor, and remainder; the idea is simple and in the air:

1. the remainder must be smaller than the divisor;
2. if you multiply the divisor by the quotient, then add the remainder, you should obtain the dividend; and
3. the answer (quotient and remainder) is unique: there is only one correct answer for each exercise in division.

For example,

• divide 11 by 4: quotient is 2, remainder is 3, so 11 = 2*4 + 3.
• divide 12 by 4: quotient is 3, remainder is 0, so 12 = 3*4.

Check that the quotients and remainders in the examples satisfy the criteria.

Quotients and remainders

The mathematical formulation of the above ideas can be proved, and is sometimes called the division theorem.

Theorem: Let D and d be integers, and d be non-zero. (We are dividing D by d.) Then for some integers quotient and remainder, we have

D = quotient * d + remainder, and
0 <= remainder < |d|;

furthermore, quotient and remainder are unique: if

D = q * d + r, and
0 <= r < |d|,

then q = quotient and r = remainder.

Proof: Deal with existence first. For natural number D, use induction. Then extend the existence to negative D. Finally, deal with the uniqueness part, noting that remainder - r must be 0.

Again, check that the examples satisfy this theorem.

If you are only interested in the natural numbers, then you do not need to worry about negative numbers, so you can drop the absolute signs above.

Multiples, divisors, and factors

If the remainder happens to be 0, i.e., for some integer quotient, we have

D = quotient * d

then we can say the followings:

• D is a multiple of d,
• d is a divisor of D,
• d divides D, abbreviated as d|D,
• d is a factor of D.

For example, 11 is not a multiple of 4, and 4 is not a divisor of 11; 12 is a multiple of 4, 4 is a divisor of 12, and 4 divides 12.

For some reasons I do not like to use the word ``factor'' in this way, but it is just a preference.

These words and concepts play a next-to-central role in number theory; therefore I take this opportunity to introduce them.