Euclidean division

<h2 id="division-theorem">Division theorem</h2>

Euclidean division is based on the following result, which is sometimes called Euclid's division lemma.
Given two integers a and b, with b ≠ 0, there exist <a href="/facts/Uniqueness_quantification/qBpdIqel">unique</a> integers q and r such that 

a = bq + r
and 

0 ≤ r < |b|,
where |b| denotes the <a href="/facts/Absolute_value/dwJBpEs5">absolute value</a> of b.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
In the above theorem, each of the four integers has a name of its own: a is called the dividend, b is called the divisor, q is called the quotient and r is called the remainder.
The computation of the quotient and the remainder from the dividend and the divisor is called division, or in case of ambiguity, Euclidean division. The theorem is frequently referred to as the division algorithm (although it is a theorem and not an algorithm), because its proof as given below lends itself to a simple division algorithm for computing q and r (see the section Proof for more).
Division is not defined in the case where b = 0; see <a href="/facts/Division_by_zero/wXK7t2Ge">division by zero</a>.
For the remainder and the <a href="/facts/Modulo_operation/V5xPUluD">modulo operation</a>, there are conventions other than 0 ≤ r < |b|, see § Other intervals for the remainder.

<h3>Generalization</h3>
Main articles: <a href="/facts/Euclidean_division_of_polynomials/4c3dUbJr">Euclidean division of polynomials</a> and <a href="/facts/Euclidean_domain/ydwCD0fz">Euclidean domain</a>
Although originally restricted to integers, Euclidean division and the division theorem can be generalized to <a href="/facts/Univariate_polynomial/Lzak8VVx">univariate polynomials</a> over a <a href="/facts/Field_(mathematics)/xAjAS4ko">field</a> and to Euclidean domains. 
In the case of <a href="/facts/Univariate_polynomial/Lzak8VVx">univariate polynomials</a>, the main difference is that the inequalities 
 
 
 
 0
 ≤
 r
 <
 
 |
 
 b
 
 |
 
 
 
 {\displaystyle 0\leq r<|b|}
 
 are replaced with

r
 =
 0
 
 
 {\displaystyle r=0}
 
 or 
 
 
 
 deg
 ⁡
 r
 <
 deg
 ⁡
 b
 ,
 
 
 {\displaystyle \deg r<\deg b,}

where 
 
 
 
 deg
 
 
 {\displaystyle \deg }
 
 denotes the <a href="/facts/Polynomial_degree/Bf8vEIhf">polynomial degree</a>.
In the generalization to Euclidean domains, the inequality becomes

r
 =
 0
 
 
 {\displaystyle r=0}
 
 or 
 
 
 
 f
 (
 r
 )
 <
 f
 (
 b
 )
 ,
 
 
 {\displaystyle f(r)<f(b),}

where 
 
 
 
 f
 
 
 {\displaystyle f}
 
 denote a specific function from the domain to the natural numbers called a "Euclidean function".
The uniqueness of the quotient and the remainder remains true for polynomials, but it is false in general.

<h2 id="history">History</h2>

Although "Euclidean division" is named after <a href="/facts/Euclid/dHpVyL4R">Euclid</a>, it seems that he did not know the existence and uniqueness theorem, and that the only computation method that he knew was the <a href="/facts/Division_algorithm/8xc3I1sJ">division by repeated subtraction</a>.
Before the invention of <a href="/facts/Hindu%E2%80%93Arabic_numeral_system/z73KvotW">Hindu–Arabic numeral system</a>, which was introduced in Europe during the 13th century by <a href="/facts/Fibonacci/d5rA6p8c">Fibonacci</a>, division was extremely difficult, and only the best mathematicians were able to do it . Presently, most <a href="/facts/Division_algorithm/8xc3I1sJ">division algorithms</a>, including <a href="/facts/Long_division/W8Vd90Kw">long division</a>, are based on this numeral system or its variants, such as <a href="/facts/Binary_numeral/a6JDSRPs">binary numerals</a>. A notable exception is <a href="/facts/Newton%E2%80%93Raphson_division/8xc3I1sJ">Newton–Raphson division</a>, which is independent from any <a href="/facts/Numeral_system/1KKlG4nd">numeral system</a>.
The term "Euclidean division" was introduced during the 20th century as a shorthand for "division of <a href="/facts/Euclidean_ring/ydwCD0fz">Euclidean rings</a>". It has been rapidly adopted by mathematicians for distinguishing this division from the other kinds of <a href="/facts/Division_(mathematics)/FqLKNkmq">division</a> of numbers.

<h2 id="intuitive-example">Intuitive example</h2>
Suppose that a pie has 9 slices and they are to be divided evenly among 4 people. Using Euclidean division, 9 divided by 4 is 2 with remainder 1. In other words, each person receives 2 slices of pie, and there is 1 slice left over.
This can be confirmed using multiplication, the inverse of division: if each of the 4 people received 2 slices, then 4 × 2 = 8 slices were given out in total. Adding the 1 slice remaining, the result is 9 slices. In summary: 9 = 4 × 2 + 1.
In general, if the number of slices is denoted 
 
 
 
 a
 
 
 {\displaystyle a}
 
 and the number of people is denoted 
 
 
 
 b
 
 
 {\displaystyle b}
 
, then one can divide the pie evenly among the people such that each person receives 
 
 
 
 q
 
 
 {\displaystyle q}
 
 slices (the quotient), with some number of slices 
 
 
 
 r
 <
 b
 
 
 {\displaystyle r<b}
 
 being the leftover (the remainder). In which case, the equation 
 
 
 
 a
 =
 b
 q
 +
 r
 
 
 {\displaystyle a=bq+r}
 
 holds.
If 9 slices were divided among 3 people instead of 4, then each would receive 3 and no slice would be left over, which means that the remainder would be zero, leading to the conclusion that 3 evenly divides 9, or that 3 <a href="/facts/Divides/DKNa2GvC">divides</a> 9.
Euclidean division can also be extended to negative dividend (or negative divisor) using the same formula; for example −9 = 4 × (−3) + 3, which means that −9 divided by 4 is −3 with remainder 3.

<h2 id="examples">Examples</h2>
<ul><li>If a = 7 and b = 3, then q = 2 and r = 1, since 7 = 3 × 2 + 1.</li>
<li>If a = 7 and b = −3, then q = −2 and r = 1, since 7 = −3 × (−2) + 1.</li>
<li>If a = −7 and b = 3, then q = −3 and r = 2, since −7 = 3 × (−3) + 2.</li>
<li>If a = −7 and b = −3, then q = 3 and r = 2, since −7 = −3 × 3 + 2.</li></ul>
<h2 id="proof">Proof</h2>
The following proof of the division theorem relies on the fact that a decreasing sequence of non-negative integers stops eventually. It is separated into two parts: one for existence and another for uniqueness of 
 
 
 
 q
 
 
 {\displaystyle q}
 
 and 
 
 
 
 r
 
 
 {\displaystyle r}
 
. Other proofs use the <a href="/facts/Well-ordering_principle/Wu64kxaT">well-ordering principle</a> (i.e., the assertion that every <a href="/facts/Nonempty_set/ffEk3eA6">non-empty set</a> of <a href="/facts/Nonnegative_integers/u65og8JE">non-negative integers</a> has a smallest element) to make the reasoning simpler, but have the disadvantage of not providing directly an algorithm for solving the division (see § Effectiveness for more).<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>

<h3>Existence</h3>
For proving the existence of Euclidean division, one can suppose 
 
 
 
 b
 >
 0
 ,
 
 
 {\displaystyle b>0,}
 
 since, if 
 
 
 
 b
 <
 0
 ,
 
 
 {\displaystyle b<0,}
 
 the equality 
 
 
 
 a
 =
 b
 q
 +
 r
 
 
 {\displaystyle a=bq+r}
 
 can be rewritten 
 
 
 
 a
 =
 (
 −
 b
 )
 (
 −
 q
 )
 +
 r
 .
 
 
 {\displaystyle a=(-b)(-q)+r.}
 
 So, if the latter equality is a Euclidean division with 
 
 
 
 −
 b
 >
 0
 ,
 
 
 {\displaystyle -b>0,}
 
 the former is also a Euclidean division.
Given 
 
 
 
 b
 >
 0
 
 
 {\displaystyle b>0}
 
 and 
 
 
 
 a
 ,
 
 
 {\displaystyle a,}
 
 there are integers 
 
 
 
 
 q
 
 1
 
 
 
 
 {\displaystyle q_{1}}
 
 and 
 
 
 
 
 r
 
 1
 
 
 ≥
 0
 
 
 {\displaystyle r_{1}\geq 0}
 
 such that 
 
 
 
 a
 =
 b
 
 q
 
 1
 
 
 +
 
 r
 
 1
 
 
 ;
 
 
 {\displaystyle a=bq_{1}+r_{1};}
 
 for example, 
 
 
 
 
 q
 
 1
 
 
 =
 0
 
 
 {\displaystyle q_{1}=0}
 
 and 
 
 
 
 
 r
 
 1
 
 
 =
 a
 
 
 {\displaystyle r_{1}=a}
 
 if 
 
 
 
 a
 ≥
 0
 ,
 
 
 {\displaystyle a\geq 0,}
 
 and otherwise 
 
 
 
 
 q
 
 1
 
 
 =
 a
 
 
 {\displaystyle q_{1}=a}
 
 and 
 
 
 
 
 r
 
 1
 
 
 =
 a
 −
 a
 b
 .
 
 
 {\displaystyle r_{1}=a-ab.}

Let 
 
 
 
 q
 
 
 {\displaystyle q}
 
 and 
 
 
 
 r
 
 
 {\displaystyle r}
 
 be such a pair of numbers for which 
 
 
 
 r
 
 
 {\displaystyle r}
 
 is nonnegative and minimal. If 
 
 
 
 r
 <
 b
 .
 
 
 {\displaystyle r<b.}
 
 we have Euclidean division. Thus, we have to prove that, if 
 
 
 
 r
 ≥
 b
 ,
 
 
 {\displaystyle r\geq b,}
 
 then 
 
 
 
 r
 
 
 {\displaystyle r}
 
 is not minimal. Indeed, if 
 
 
 
 r
 ≥
 b
 ,
 
 
 {\displaystyle r\geq b,}
 
 one has 
 
 
 
 a
 =
 b
 (
 q
 +
 1
 )
 +
 (
 r
 −
 b
 )
 ,
 
 
 {\displaystyle a=b(q+1)+(r-b),}
 
 with 
 
 
 
 0
 ≤
 r
 −
 b
 <
 r
 ,
 
 
 {\displaystyle 0\leq r-b<r,}
 
 and 
 
 
 
 r
 
 
 {\displaystyle r}
 
 is not minimal
This proves the existence in all cases. This provides also an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> for computing the quotient and the remainder, by starting from 
 
 
 
 q
 =
 0
 
 
 {\displaystyle q=0}
 
 (if 
 
 
 
 a
 ≥
 0
 
 
 {\displaystyle a\geq 0}
 
) and adding 
 
 
 
 1
 
 
 {\displaystyle 1}
 
 to it until 
 
 
 
 a
 −
 b
 q
 <
 b
 .
 
 
 {\displaystyle a-bq<b.}
 
 However, this algorithm is not efficient, since its number of steps is of the order of 
 
 
 
 a
 
 /
 
 b
 
 
 {\displaystyle a/b}

<h3>Uniqueness</h3>
The pair of integers r and q such that a = bq + r is unique, in the sense that there can be no other pair of integers that satisfy the same condition in the Euclidean division theorem. In other words, if we have another division of a by b, say a = bq' + r' with 0 ≤ r' < |b|, then we must have that

q' = q and r' = r.
To prove this statement, we first start with the assumptions that

0 ≤ r < |b|
0 ≤ r' < |b|
a = bq + r
a = bq' + r' 
Subtracting the two equations yields

b(q – q′) = r′ – r.
So b is a divisor of r′ – r. As 

|r′ – r| < |b|
by the above inequalities, one gets 

r′ – r = 0,
and 

b(q – q′) = 0.
Since b ≠ 0, we get that r = r′ and q = q′, which proves the uniqueness part of the Euclidean division theorem.

<h2 id="effectiveness">Effectiveness</h2>
In general, an existence proof does not provide an algorithm for computing the existing quotient and remainder, but the above proof does immediately provide an algorithm (see <a href="/facts/Division_algorithm/8xc3I1sJ">Division algorithm#Division by repeated subtraction</a>), even though it is not a very efficient one as it requires as many steps as the size of the quotient. This is related to the fact that it uses only additions, subtractions and comparisons of integers, without involving multiplication, nor any particular representation of the integers such as decimal notation.
In terms of decimal notation, <a href="/facts/Long_division/W8Vd90Kw">long division</a> provides a much more efficient algorithm for solving Euclidean divisions. Its generalization to <a href="/facts/Binary_number/a6JDSRPs">binary</a> and <a href="/facts/Hexadecimal/02ohQW22">hexadecimal</a> notation provides further flexibility and possibility for computer implementation. However, for large inputs, algorithms that reduce division to multiplication, such as <a href="/facts/Division_algorithm/8xc3I1sJ">Newton–Raphson</a>, are usually preferred, because they only need a time which is proportional to the time of the multiplication needed to verify the result—independently of the multiplication algorithm which is used (for more, see <a href="/facts/Division_algorithm/8xc3I1sJ">Division algorithm#Fast division methods</a>).

<h2 id="variants">Variants</h2>
The Euclidean division admits a number of variants, some of which are listed below.

<h3>Other intervals for the remainder</h3>
See also: <a href="/facts/Modulo_operation/V5xPUluD">Modulo operation § Variants of the definition</a>
In Euclidean division with d as divisor, the remainder is supposed to belong to the <a href="/facts/Interval_(mathematics)/e9se3vTe">interval</a> [0, d) of length |d|. Any other interval of the same length may be used. More precisely, given integers 
 
 
 
 m
 
 
 {\displaystyle m}
 
, 
 
 
 
 a
 
 
 {\displaystyle a}
 
, 
 
 
 
 d
 
 
 {\displaystyle d}
 
 with 
 
 
 
 m
 >
 0
 
 
 {\displaystyle m>0}
 
, there exist unique integers 
 
 
 
 q
 
 
 {\displaystyle q}
 
 and 
 
 
 
 r
 
 
 {\displaystyle r}
 
 with 
 
 
 
 d
 ≤
 r
 <
 m
 +
 d
 
 
 {\displaystyle d\leq r<m+d}
 
 such that 
 
 
 
 a
 =
 m
 q
 +
 r
 
 
 {\displaystyle a=mq+r}
 
.
In particular, if 
 
 
 
 d
 =
 −
 
 ⌊
 
 
 m
 2
 
 
 ⌋
 
 
 
 {\displaystyle d=-\left\lfloor {\frac {m}{2}}\right\rfloor }
 
 then 
 
 
 
 −
 
 ⌊
 
 
 m
 2
 
 
 ⌋
 
 ≤
 r
 <
 m
 −
 
 ⌊
 
 
 m
 2
 
 
 ⌋
 
 
 
 {\displaystyle -\left\lfloor {\frac {m}{2}}\right\rfloor \leq r<m-\left\lfloor {\frac {m}{2}}\right\rfloor }
 
 . This division is called the centered division, and its remainder 
 
 
 
 r
 
 
 {\displaystyle r}
 
 is called the centered remainder or the least absolute remainder.
This is used for approximating <a href="/facts/Real_number/R02gw5Pb">real numbers</a>: Euclidean division defines <a href="/facts/Truncation/8mEHh0qp">truncation</a>, and centered division defines <a href="/facts/Rounding/rCLYXN00">rounding</a>.

<h3>Montgomery division</h3>
Main article: <a href="/facts/Montgomery_modular_multiplication/C1UyVrKJ">Montgomery modular multiplication</a>
Given integers 
 
 
 
 a
 
 
 {\displaystyle a}
 
, 
 
 
 
 m
 
 
 {\displaystyle m}
 
 and 
 
 
 
 R
 ,
 
 
 {\displaystyle R,}
 
 with 
 
 
 
 m
 >
 0
 
 
 {\displaystyle m>0}
 
 and 
 
 
 
 gcd
 (
 R
 ,
 m
 )
 =
 1
 ,
 
 
 {\displaystyle \gcd(R,m)=1,}
 
 let 
 
 
 
 
 R
 
 −
 1
 
 
 
 
 {\displaystyle R^{-1}}
 
 be the <a href="/facts/Modular_multiplicative_inverse/xs8VgHPa">modular multiplicative inverse</a> of 
 
 
 
 R
 
 
 {\displaystyle R}
 
 (i.e., 
 
 
 
 0
 <
 
 R
 
 −
 1
 
 
 <
 m
 
 
 {\displaystyle 0<R^{-1}<m}
 
 with 
 
 
 
 
 R
 
 −
 1
 
 
 R
 −
 1
 
 
 {\displaystyle R^{-1}R-1}
 
 being a multiple of 
 
 
 
 m
 
 
 {\displaystyle m}
 
), then there exist unique integers 
 
 
 
 q
 
 
 {\displaystyle q}
 
 and 
 
 
 
 r
 
 
 {\displaystyle r}
 
 with 
 
 
 
 0
 ≤
 r
 <
 m
 
 
 {\displaystyle 0\leq r<m}
 
 such that 
 
 
 
 a
 =
 m
 q
 +
 
 R
 
 −
 1
 
 
 ⋅
 r
 
 
 {\displaystyle a=mq+R^{-1}\cdot r}
 
.
This result generalizes Hensel's odd division (1900).<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>
The value 
 
 
 
 r
 
 
 {\displaystyle r}
 
 is the N-residue defined in <a href="/facts/Montgomery_reduction/C1UyVrKJ">Montgomery reduction</a>.

<h2 id="in-euclidean-domains">In Euclidean domains</h2>
See also: <a href="/facts/Polynomial_long_division/MgJlJ2G7">Polynomial long division</a>, <a href="/facts/Polynomial_greatest_common_divisor/4c3dUbJr">Polynomial greatest common divisor § Euclidean division</a>, and <a href="/facts/Polynomial_greatest_common_divisor/4c3dUbJr">Polynomial greatest common divisor § Pseudo-remainder sequences</a>
<a href="/facts/Euclidean_domain/ydwCD0fz">Euclidean domains</a> (also known as Euclidean rings)<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> are defined as <a href="/facts/Integral_domain/cylt6zxW">integral domains</a> which support the following generalization of Euclidean division:

Given an element a and a non-zero element b in a Euclidean domain R equipped with a Euclidean function d (also known as a Euclidean valuation<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a> or degree function<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>), there exist q and r in R such that a = bq + r and either r = 0 or d(r) < d(b).
Uniqueness of q and r is not required.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a> It occurs only in exceptional cases, typically for <a href="/facts/Univariate_polynomial/Lzak8VVx">univariate polynomials</a>, and for integers, if the further condition r ≥ 0 is added.
Examples of Euclidean domains include <a href="/facts/Field_(mathematics)/xAjAS4ko">fields</a>, <a href="/facts/Polynomial_ring/ua3vk8Ih">polynomial rings</a> in one variable over a field, and the <a href="/facts/Gaussian_integers/zj82AhtL">Gaussian integers</a>. The Euclidean division of polynomials has been the object of specific developments.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Euclid%27s_lemma/SlsXGAmD">Euclid's lemma</a></li>
<li><a href="/facts/Euclidean_algorithm/wApql29c">Euclidean algorithm</a></li></ul>
<h2 id="notes">Notes</h2>

<ul><li>Fraleigh, John B. (1993), A First Course in Abstract Algebra (5th ed.), Addison-Wesley, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-201-53467-2</li>
<li>Rotman, Joseph J. (2006), A First Course in Abstract Algebra with Applications (3rd ed.), Prentice-Hall, <a href="/facts/ISBN_(identifier)/15AdSPa9">ISBN</a> 978-0-13-186267-8</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">"Division and Euclidean algorithms". www-groups.mcs.st-andrews.ac.uk. Archived from the original on 2021-05-06. Retrieved 2019-11-15. <a href="https://web.archive.org/web/20210506140331/http://www-groups.mcs.st-andrews.ac.uk/~john/MT4517/Lectures/L6.html" target="_blank">https://web.archive.org/web/20210506140331/http://www-groups.mcs.st-andrews.ac.uk/~john/MT4517/Lectures/L6.html</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">"What is modular arithmetic?". Khan Academy. Retrieved 2019-11-15. <a href="https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic" target="_blank">https://www.khanacademy.org/computing/computer-science/cryptography/modarithmetic/a/what-is-modular-arithmetic</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">"Fun With Modular Arithmetic – BetterExplained". betterexplained.com. Retrieved 2019-11-15. <a href="https://betterexplained.com/articles/fun-with-modular-arithmetic/" target="_blank">https://betterexplained.com/articles/fun-with-modular-arithmetic/</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Burton, David M. (2010). Elementary Number Theory. McGraw-Hill. pp. 17–19. ISBN 978-0-07-338314-9. <a href="978-0-07-338314-9" target="_blank">978-0-07-338314-9</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Durbin, John R. (1992). Modern Algebra : an Introduction (3rd ed.). New York: Wiley. p. 63. ISBN 0-471-51001-7. <a href="0-471-51001-7" target="_blank">0-471-51001-7</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Haining Fan; Ming Gu; Jiaguang Sun; Kwok-Yan Lam (2012). "Obtaining More Karatsuba-Like Formulae over the Binary Field". IET Information Security. 6 (1): 14–19. CiteSeerX 10.1.1.215.1576. doi:10.1049/iet-ifs.2010.0114. <a href="/wiki/CiteSeerX_(identifier)" target="_blank">/wiki/CiteSeerX_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">Rotman 2006, p. 267 - Rotman, Joseph J. (2006), A First Course in Abstract Algebra with Applications (3rd ed.), Prentice-Hall, ISBN 978-0-13-186267-8 <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Fraleigh 1993, p. 376 - Fraleigh, John B. (1993), A First Course in Abstract Algebra (5th ed.), Addison-Wesley, ISBN 978-0-201-53467-2 <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Rotman 2006, p. 267 - Rotman, Joseph J. (2006), A First Course in Abstract Algebra with Applications (3rd ed.), Prentice-Hall, ISBN 978-0-13-186267-8 <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">"Division and Euclidean algorithms". www-groups.mcs.st-andrews.ac.uk. Archived from the original on 2021-05-06. Retrieved 2019-11-15. <a href="https://web.archive.org/web/20210506140331/http://www-groups.mcs.st-andrews.ac.uk/~john/MT4517/Lectures/L6.html" target="_blank">https://web.archive.org/web/20210506140331/http://www-groups.mcs.st-andrews.ac.uk/~john/MT4517/Lectures/L6.html</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
</ol>

Euclidean division open-in-new

Euclidean division