Division algorithm
From Maths
Revision as of 07:36, 21 May 2015 by Alec (Talk | contribs) (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 {{...")
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
TODO:
See also
References
- ↑ The mathematics of ciphers, Number theory and RSA cryptography - S. C. Coutinho
