Table of Contents

Last modified on April 26th, 2024

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.

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.

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

As we know, for the integers â€˜qâ€™ and â€˜râ€™ as defined above, a = b â‹… q + r and 0 â‰¤ r < bâ€¦..(iii)

Let â€˜q_{1}â€™ and â€˜r_{1}â€™ be any two integers such that a = b â‹… q_{1} + r_{1} and 0 â‰¤ r_{1} < bâ€¦..(iv)

By substituting both the values of a from (iii) and (iv), we get b â‹… q + r = b â‹… q_{1} + r_{1}

â‡’ r – r_{1} = b â‹… q_{1} – b â‹… q = b(q_{1} – q)

r – r_{1} = b(q_{1} – q)…..(v)

Let us assume that r_{1} â‰¥ r

Since 0 â‰¤ r_{1} – r â‰¤ r_{1} and r_{1} < b,

0 â‰¤ r_{1} – r < b

From (v), we get

0 â‰¤ b(q – q_{1}) < b

â‡’ 0 â‰¤ q – q_{1} < 1

Since q – q_{1} is an integer such that 0 â‰¤ q – q_{1} < 1

Then q – q_{1} = 0

â‡’ q = q_{1}

Now, if we assume r â‰¥ r_{1}

By a similar argument, we get q = q_{1}

Thus, q = q_{1}, in general

â‡’ q – q_{1} = 0

Here, r_{1} – r = b(q – q_{1})

â‡’ r_{1} – r = b â‹… 0 = 0

â‡’ r_{1} = r

Thus, q = q_{1} and r = r_{1} show that â€˜qâ€™ and â€˜râ€™ are unique.

**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.

Last modified on April 26th, 2024