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 [ilmath]0\le r < b[/ilmath] actually holds, and adds one to [ilmath]q[/ilmath] 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, [ilmath]a\in\mathbb{N} [/ilmath] and [ilmath]b\in\mathbb{N}_+[/ilmath], we wish to compute [ilmath]a\div b[/ilmath] (with remainder), we say "[ilmath]a[/ilmath] divided by [ilmath]b[/ilmath]", we call:

• [ilmath]a[/ilmath] the dividend (the "numerator" of the fraction [ilmath]\tfrac{a}{b} [/ilmath])
• [ilmath]b[/ilmath] the divisor (the "denominator" of the fraction [ilmath]\tfrac{a}{b} [/ilmath])

The outputs are two integers [ilmath]q\in\mathbb{N} [/ilmath] and [ilmath]r\in\mathbb{N} [/ilmath] such that:

• [math]a=bq+r[/math] with [math]0\le r< b[/math]

We call:

• [ilmath]q[/ilmath] the quotient
• [ilmath]r[/ilmath] the remainder

Important theorems

Theorem: For a given [ilmath]a,b[/ilmath] the [ilmath]q[/ilmath] and [ilmath]r[/ilmath] are unique, regardless of how they are computed

---

Suppose that we have:

• [math]a=bq+r[/math] with [math]0\le r< b[/math]
• [math]a=bq'+r'[/math] with [math]0\le r'<b[/math]

Suppose [math]r\ge r'[/math] (WLOG - swap them around if this isn't true)

Then by subtraction we see [math]r-r'=(a-bq)-(a-bq')[/math]

[math]\implies r-r'=bq'-bq[/math]

[math]\implies r-r'=b(q'-q)[/math]

Recall that [math]0\le r< b[/math] and [math]r\ge r'[/math]

The latter means that [math]r-r'\ge 0[/math] (or [math]0\le r-r'[/math])

We know that [math]r< b[/math]

[math]\implies r-r' < b-r'[/math]

As [math]r'\ge 0[/math] we see that [math]-r'\ge 0[/math]

So [math]\implies r-r` < b-r' \le b[/math]

Or simply [math]\implies r-r'< b[/math]

Combining [math]r-r'< b[/math] and [math]0\le r-r'[/math] we see:

[math]0\le r-r'< b[/math]

But we know [math]r-r'=b(q'-q)[/math]

So [math]0\le b(q'-q)< b[/math]

Dividing by [ilmath]b[/ilmath] we see [math]0\le q'-q < 1[/math]

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

Thus we conclude [math]q'-q=0[/math]

[math]\implies q'=q[/math]

We need to show [math]r=r'[/math] now.

Recall that [math]a=bq+r[/math] and [math]a=bq'+r'[/math]

We can combine these to see: [math]bq+r=bq'+r'[/math]

but we know from above that [math]q=q'[/math]

So [math]bq+r=bq+r'[/math]

using the cancellation laws of a ring we see

[math]bq+r=bq+r'\implies r=r'[/math]

Or indeed by subtracting [math]bq[/math] from both sides, as usual.

The claim [math]r=r'[/math] is shown

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

See also

• GCD
• Euclidean algorithm