Quotient Remainder Theorem

The quotient remainder theorem states that if any integer ‘a’ is divided by any positive non-zero integer ‘b,’ there exist unique integers ‘q’ and ‘r’ such that: 

a = b ⋅ q + r, here 0 ≤ r < b

It supports modular arithmetic, where we use the mod operation to establish rules for adding and multiplying numbers under this system, among other arithmetic operations. 

Proof

First, we show that for any integer ‘a’ and positive integer ‘b,’ a quotient ‘q’ and a remainder ‘r’ exist, and then we verify that ‘q’ and ‘r’ are unique.

Verifying the Existence of Solution

Let ‘a’ be any integer and ‘b’ be any positive non-zero integer.

Let S be a set defined as

S = {x Є ℤ | x ≥ 0 and x = a – b ⋅ k, for some integer k}

There are two possibilities of ‘a’: either a ≥ 0 or a < 0

Considering a ≥ 0

If k = 0, then a – b ⋅ k = a ≥ 0 ⇒ a = (a – b ⋅ k) Є S

Thus, the set S is non-empty if a ≥ 0…..(i)

Again, considering a < 0 ⇒ -a > 0

Since b ≥ 1, b – 1 > 0

Thus, (-a) ⋅ (b – 1) ≥ 0

If k = a, a – b ⋅ k = a – b ⋅ a = (-a) ⋅ (b – 1) ≥ 0 ⇒ (a – b ⋅ k)  Є S

Thus, the set S is non-empty if a < 0…..(ii)

From (i) and (ii), we conclude that S is generally non-empty.

By definition of the set S, every element in S is greater than or equal to 0

Thus, S satisfies the conditions of the Well-Ordering Principle, and S contains at least ‘p’

Since p Є S, there is some integer ‘m’ such that p = a – b ⋅ m ⇒ a = p + b ⋅ m

Since p Є S, p ≥ 0

If possible, let p ≥ b ⇒ p – b ≥ 0

Now, p – b = (a – b ⋅ m) – b = a – b ⋅ (m + 1)

⇒ p – b = a – b ⋅ k, where k = m + 1

Thus, p – b ≥ 0 and p – b = a – b ⋅ k, for some integer ‘k’, which proves p – b Є S

However, p – b < p, which contradicts that ‘p’ is the least element of the set S

Thus, p < b

Here, a = b ⋅ m + p and 0 ≤ p < b

If q = m and r = p, then ‘q’ and ‘r’ are integers such that a = b ⋅ q + r and 0 ≤ r < b

Verifying the Uniqueness of Solution

As we know, for the integers ‘q’ and ‘r’ as defined above, a = b ⋅ q + r and 0 ≤ r < b…..(iii)

Let ‘q₁’ and ‘r₁’ be any two integers such that a = b ⋅ q₁ + r₁ and 0 ≤ r₁ < b…..(iv)

By substituting both the values of a from (iii) and (iv), we get b ⋅ q + r = b ⋅ q₁ + r₁

⇒ r – r₁ = b ⋅ q₁ – b ⋅ q = b(q₁ – q)

r – r₁ = b(q₁ – q)…..(v)

Let us assume that r₁ ≥ r

Since 0 ≤ r₁ – r ≤ r₁ and r₁ < b, 

0 ≤ r₁ – r < b

From (v), we get

0 ≤ b(q – q₁) < b

⇒ 0 ≤ q – q₁ < 1

Since q – q₁ is an integer such that 0 ≤ q – q₁ < 1

Then q – q₁ = 0

⇒ q = q₁

Now, if we assume r ≥ r₁

By a similar argument, we get q = q₁

Thus, q = q₁, in general

⇒ q – q₁ = 0

Here, r₁ – r = b(q – q₁)

⇒ r₁ – r = b ⋅ 0 = 0

⇒ r₁ = r

Thus, q = q₁ and r = r₁ show that ‘q’ and ‘r’ are unique.

Solved Example