Understanding Division Algorithm

In this class, We discuss Understanding Division Algorithm.

The reader can take complete discrete mathematics and graph theory courses. Click Here.

Let a and b be any two integers (b > 0)

For each a, b. We have unique integers q and r such that a = bq + r. (0 <= r < b)

The graphical intuition of why the formulae a = bq + r works is shown below.

“a” is equal or lies between two consecutive multiples of b.

qb <= a < (q+1)b

Uniqueness of q and r.

Assume “a” can be expressed in more than one way.

a = q1b + r1

a = q2b + r2

In the end, we show our assumption is false

From the above equations

q1b + r1 = q2b + r2

r1 – r2 = (q2 – q1)b

The above equation shows b divides r1 – r2.

But b does not divide r1 – r2 because r1 and r2 are values less than b. 

Our assumption that “a” can be expressed in two ways is false.