Division algorithm

Grade: A*

This page requires some work to be carried out

Some aspect of this page is incomplete and work is required to finish it
The message provided is:

Tasks:

• Move definition of integer division to own page Alec (talk) 16:48, 7 December 2017 (UTC)
• Add algorithm - it's the crappy one that just subtracts until $0\le r < b$ actually holds, and adds one to $q$ each iteration Alec (talk) 16:48, 7 December 2017 (UTC)
• Move proof of uniqueness of divisor and remainder into own page Alec (talk) 16:48, 7 December 2017 (UTC)
• Work on negative numbers Alec (talk) 16:48, 7 December 2017 (UTC)

Definition

Given two positive integers, $a\in\mathbb{N}$ and $b\in\mathbb{N}_+$, we wish to compute $a\div b$ (with remainder), we say "$a$ divided by $b$", we call:

• $a$ the dividend (the "numerator" of the fraction $\tfrac{a}{b}$)
• $b$ the divisor (the "denominator" of the fraction $\tfrac{a}{b}$)

The outputs are two integers $q\in\mathbb{N}$ and $r\in\mathbb{N}$ such that:

• $$a=bq+r$$ with $$0\le r< b$$

We call:

• $q$ the quotient
• $r$ the remainder

Important theorems

[Expand]

Theorem: For a given $a,b$ the $q$ and $r$ are unique, regardless of how they are computed

---

Suppose that we have:

• $$a=bq+r$$ with $$0\le r< b$$
• $$a=bq'+r'$$ with $$0\le r'<b$$

Suppose $$r\ge r'$$ (WLOG - swap them around if this isn't true)

Then by subtraction we see $$r-r'=(a-bq)-(a-bq')$$

$$\implies r-r'=bq'-bq$$

$$\implies r-r'=b(q'-q)$$

Recall that $$0\le r< b$$ and $$r\ge r'$$

The latter means that $$r-r'\ge 0$$ (or $$0\le r-r'$$ )

We know that $$r< b$$

$$\implies r-r' < b-r'$$

As $$r'\ge 0$$ we see that $$-r'\ge 0$$

So $$\implies r-r` < b-r' \le b$$

Or simply $$\implies r-r'< b$$

Combining $$r-r'< b$$ and $$0\le r-r'$$ we see:

$$0\le r-r'< b$$

But we know $$r-r'=b(q'-q)$$

So $$0\le b(q'-q)< b$$

Dividing by $b$ we see $$0\le q'-q < 1$$

As the integers are a ring, we know that $$q'-q\in\mathbb{Z}$$ and the only integers in the range $$0\le i< 1$$ is $$0$$ itself

Thus we conclude $$q'-q=0$$

$$\implies q'=q$$

We need to show $$r=r'$$ now.

Recall that $$a=bq+r$$ and $$a=bq'+r'$$

We can combine these to see: $$bq+r=bq'+r'$$

but we know from above that $$q=q'$$

So $$bq+r=bq+r'$$

using the cancellation laws of a ring we see

$$bq+r=bq+r'\implies r=r'$$

Or indeed by subtracting $$bq$$ from both sides, as usual.

The claim $$r=r'$$ is shown

We have now shown that if $$a=bq+r$$ and $$a=bq'+r'$$ with $$0\le r< 0$$ and $$0\le r'< 0$$ then we must have $$q=q'$$ and $$r=r'$$ - as required.

See also

• GCD
• Euclidean algorithm