Difference between revisions of "Division algorithm"
From Maths
m (→Important theorems) |
m (Saving note to clean up) |
||
| Line 1: | Line 1: | ||
| − | + | {{Requires work|grade=A*|msg=Tasks: | |
| + | * Move definition of [[integer division]] to own page [[User:Alec|Alec]] ([[User talk:Alec|talk]]) 16:48, 7 December 2017 (UTC) | ||
| + | * Add algorithm - it's the crappy one that just subtracts until {{M|0\le r < b}} actually holds, and adds one to {{M|q}} each iteration [[User:Alec|Alec]] ([[User talk:Alec|talk]]) 16:48, 7 December 2017 (UTC) | ||
| + | * Move proof of uniqueness of divisor and remainder into own page [[User:Alec|Alec]] ([[User talk:Alec|talk]]) 16:48, 7 December 2017 (UTC) | ||
| + | * Work on negative numbers [[User:Alec|Alec]] ([[User talk:Alec|talk]]) 16:48, 7 December 2017 (UTC) | ||
| + | }} | ||
| + | __TOC__ | ||
==Definition== | ==Definition== | ||
Given two positive integers, {{M|a\in\mathbb{N} }} and {{M|b\in\mathbb{N}_+}}, we wish to compute {{M|a\div b}} (with remainder), we say "{{M|a}} divided by {{M|b}}"<ref>The mathematics of ciphers, Number theory and RSA cryptography - S. C. Coutinho</ref>, we call: | Given two positive integers, {{M|a\in\mathbb{N} }} and {{M|b\in\mathbb{N}_+}}, we wish to compute {{M|a\div b}} (with remainder), we say "{{M|a}} divided by {{M|b}}"<ref>The mathematics of ciphers, Number theory and RSA cryptography - S. C. Coutinho</ref>, we call: | ||
Latest revision as of 16:48, 7 December 2017
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:
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]"[1], 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]
- [math]\implies r-r' < b-r'[/math]
- Combining [math]r-r'< b[/math] and [math]0\le r-r'[/math] we see:
- Recall that [math]0\le r< b[/math] and [math]r\ge r'[/math]
- [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
- So [math]0\le b(q'-q)< b[/math]
- 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.
- but we know from above that [math]q=q'[/math]
- We can combine these to see: [math]bq+r=bq'+r'[/math]
- Recall that [math]a=bq+r[/math] and [math]a=bq'+r'[/math]
- 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
References
- ↑ The mathematics of ciphers, Number theory and RSA cryptography - S. C. Coutinho
