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 (→Important theorems) |
||
| Line 15: | Line 15: | ||
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}} | ||
Revision as of 11:25, 21 May 2015
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
