View source for Division algorithm


==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:
* {{M|a}} the dividend (the "numerator" of the fraction {{M|\tfrac{a}{b} }})
* {{M|b}} the divisor (the "denominator" of the fraction {{M|\tfrac{a}{b} }})

The outputs are two integers {{M|q\in\mathbb{N} }} and {{M|r\in\mathbb{N} }} such that:
* <math>a=bq+r</math> with <math>0\le r< b</math>
We call:
* {{M|q}} the ''quotient''
* {{M|r}} the ''remainder''

==Important theorems==
{{Begin Theorem}}
Theorem: For a given {{M|a,b}} the {{M|q}} and {{M|r}} are unique, regardless of how they are computed
{{Begin Proof}}
{{Todo}}
{{End Proof}}{{End Theorem}}

==See also==
* [[GCD]]
* [[Euclidean algorithm]]

==References==
<references/>

{{Definition|Number Theory}}