# 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 â€˜q1â€™ and â€˜r1â€™ be any two integers such that a = b â‹… q1 + r1 and 0 â‰¤ r1 < bâ€¦..(iv)

By substituting both the values of a from (iii) and (iv), we get b â‹… q + r = b â‹… q1 + r1

â‡’ r – r1 = b â‹… q1 – b â‹… q = b(q1 – q)

r – r1 = b(q1 – q)…..(v)

Let us assume that r1 â‰¥ r

Since 0 â‰¤ r1 – r â‰¤ r1 and r1 < b,

0 â‰¤ r1 – r < b

From (v), we get

0 â‰¤ b(q – q1) < b

â‡’ 0 â‰¤ q – q1 < 1

Since q – q1 is an integer such that 0 â‰¤ q – q1 < 1

Then q – q1 = 0

â‡’ q = q1

Now, if we assume r â‰¥ r1

By a similar argument, we get q = q1

Thus, q = q1, in general

â‡’ q – q1 = 0

Here, r1 – r = b(q – q1)

â‡’ r1 – r = b â‹… 0 = 0

â‡’ r1 = r

Thus, q = q1 and r = r1 show that â€˜qâ€™ and â€˜râ€™ are unique.

## Solved Example

Using the quotient-remainder theorem, compute â€˜q,â€™ the quotient, and â€˜r,â€™ the remainder, given â€˜aâ€™ is divided by â€˜b,â€™ and also verify that a = b â‹… q + r
a) a = 182, b = 9
b) a = -181, b = 7
c) a = 529, b = 23

Solution:

a) When a = 182 is divided b = 9, we get the quotient q = 20 and the remainder r = 2
Also, 182 = 9 â‹… 20 + 2
â‡’ a = b â‹… q + r, verified.
b) When a = -181 is divided b = 7, we get the quotient q = -25 and the remainder r = 6
Also, -181 = 7 â‹… (-25) + 6
â‡’ a = b â‹… q + r, verified.
c) When a = 529 is divided b = 23, we get the quotient q = 23 and the remainder r = 0
Also, 529 = 23 â‹… 23 + 0
â‡’ a = b â‹… q + r, verified.