Division with remainder

Theorem (division with remainder)

Let , . There exist unique integers and such that and . is called the quotient and is called the remainder of the division of by . The procedure of finding and is called division with remainder.

Before actually proving division with remainder, let us have a taste of the theorem by looking at some examples:

Example

Dividing by with remainder gives . Here, the quotient is and the remainder is . But! Dividing by with remainder gives . Here, the quotient is and the remainder is .

The intuition of dividing with remainder for negative numbers is “how many copies of the divisor can we subtract from the dividend to get a non-negative number”. The remainder is the number left after we subtracted as many copies of the divisor as possible. The best way to illustrate it is to draw a number line and observe the quotient and remainder geometrically.

The proof will proceed by induction on . Before you proceed, try to prove on your own.

Proof of existence

Let , . Let us find such numbers and that while . We will start with the case where and . We will proceed by induction on .

Base case: .

If , then .

If , then , and .

Step of the induction

Let us assume that for some we found , (induction assumption). Let us find the decomposition for . If , then and . If , then and . We were able to explicitly present a decomposition of using the decomposition of . This completes the proof of existence.

Exercise or .

Complete the proof for negative or zero

The proof will proceed by contradiction. Before you proceed, try to prove on your own.

Proof of uniqueness

As most uniqueness proofs given existence, we proceed by contradiction. Since we know that a decomposition exists, the converse of uniqueness would be “there exist two different decompositions of “. Let us assume that where . We then get that

Assume the pairs and are different: this is our assumption for proof by contradiction. If , then equality gives . However, this leads to a contradiction with our assumption that the pairs are different. If , then . This leads to a contradiction with the fact that . Therefore, the assumption that the pairs are different is incorrect, and the decomposition is unique.

Corollary

A number is divisible by if and only if the remainder of the division of by is .

Exercise

Prove the corollary.