Difference between revisions of "Division algorithm"
From Maths
(Created page with " ==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 (Saving note to clean up) |
||
| (One intermediate revision by the same user not shown) | |||
| 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: | ||
| Line 15: | Line 21: | ||
Theorem: For a given {{M|a,b}} the {{M|q}} and {{M|r}} are unique, regardless of how they are computed | Theorem: For a given {{M|a,b}} the {{M|q}} and {{M|r}} are unique, regardless of how they are computed | ||
{{Begin Proof}} | {{Begin Proof}} | ||
| − | {{ | + | 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 {{M|b}} 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 [[Ring#Important theorems|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. | ||
| + | |||
{{End Proof}}{{End Theorem}} | {{End Proof}}{{End Theorem}} | ||
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
