View source for Long division

{{short description|Standard division algorithm for multi-digit numbers}}
{{about|elementary handwritten division|mathematical definition and properties|Division (mathematics)|and|Euclidean division|software algorithms|Division algorithm|other uses}}

In [[arithmetic]], '''long division''' is a standard [[division algorithm]] suitable for dividing multi-digit [[Hindu–Arabic numeral system|Hindu-Arabic numerals]] ([[positional notation]]) that is simple enough to perform by hand. It breaks down a [[division (mathematics)|division]] problem into a series of easier steps.

As in all division problems, one number, called the [[division (mathematics)|dividend]], is divided by another, called the [[divisor]],  producing a result called the [[quotient]]. It enables computations involving arbitrarily large numbers to be performed by following a series of simple steps.<ref>{{MathWorld | urlname=LongDivision | title= Long Division}}</ref> The abbreviated form of long division is called [[short division]], which is almost always used{{citation-needed|date=November 2025}} instead of long division when the divisor has only one digit.

==History==

Related algorithms have existed since the 12th century.<ref>{{Cite web|url=http://new.math.uiuc.edu/im2008/rogers/algebra.html|title=Islamic Mathematics|website=new.math.uiuc.edu|access-date=2016-03-31}}</ref>
[[Al-Samawal al-Maghribi]] (1125–1174) performed calculations with decimal numbers that essentially require long division, leading to infinite decimal results, but without formalizing the algorithm.<ref>Victor J. Katz, A History of Mathematics: An Introduction, Addison-Wesley, 2008</ref>
Caldrini (1491) is the earliest printed example of long division, known as the ''Danda'' method in medieval Italy,<ref>{{Cite web|url=https://research-repository.griffith.edu.au/bitstream/handle/10072/2509/29769.pdf?sequence=1|title=A Historical Analysis of the Division Concept|author=Will Windsor and George Booker|year=2005}}</ref> and it became more practical with the introduction of decimal notation for fractions by [[Bartholomaeus Pitiscus|Pitiscus]] (1608).
The specific algorithm in modern use was introduced by [[Henry Briggs (mathematician)|Henry Briggs]] {{Circa}} 1600.<ref>{{Cite book|title=Henry Briggs - Oxford Reference|url=http://www.oxfordreference.com/view/10.1093/oi/authority.20110810104516866}}</ref>

== Education ==
{{globalize|date=May 2024}}
Inexpensive calculators and computers have become the most common way to solve division problems, eliminating a traditional [[mathematical exercise]] and decreasing the educational opportunity to show how to do so by paper and pencil techniques. (Internally, those devices use one of a variety of [[division algorithm]]s, the faster of which rely on approximations and multiplications to achieve the tasks.) In North America, long division has been especially targeted for de-emphasis or even elimination from the school curriculum by [[reform mathematics]], though it has been traditionally introduced in the 4th, 5th or even 6th grades.<ref>{{Cite web|url=http://www.csun.edu/~vcmth00m/longdivision.pdf|title=The Role of Long Division in the K-12 Curriculum|last=Klein, Milgram|website=CiteSeer|access-date=June 21, 2019}}</ref>

== Method ==
In English-speaking countries, long division does not use the [[division slash]] {{angle brackets|[[∕]]}} or [[division sign]] {{angle brackets|÷}} symbols but instead constructs a '''tableau'''.<ref>{{citation |last=Nicholson |first=W. Keith |title=Introduction to Abstract Algebra, ''4th ed.'' |publisher=John Wiley & Sons |date=2012 |page=[https://books.google.com/books?id=w-GaLpapRcEC&pg=PA206 206] }}.</ref> The [[divisor]] is separated from the dividend by a [[right parenthesis]] {{angle brackets|[[)]]}} or [[vertical bar]] {{angle brackets|[[vertical bar|{{!}}]]}}; the dividend is separated from the [[quotient]] by a [[Vinculum (symbol)|vinculum]] (i.e., an [[overbar]]). The combination of these two symbols is sometimes known as a '''long division symbol''' or '''division bracket'''.<ref>{{citation |title=Wolfram MathWorld |contribution-url=http://mathworld.wolfram.com/LongDivisionSymbol.html |contribution=Long Division Symbol |url=http://wolfram.com |access-date=11 February 2016 }}.</ref> It developed in the 18th century from an earlier single-line notation separating the dividend from the quotient by a [[left parenthesis]].<ref>{{citation |contribution=Symbols of Operation |contribution-url=https://jeff560.tripod.com/operation.html |date=2010 |url=https://mathshistory.st-andrews.ac.uk/Miller/mathsym/ |title=Earliest Uses of Various Mathematical Symbols |last=Miller |first=Jeff }}.</ref><ref>{{citation |last=Hill|first=John|title=Arithmetick both in the theory and practice|publisher=Straben et al.|year=1772|edition=11th|orig-year=First published 1712|place=London|url=http://digital.library.pitt.edu/cgi-bin/t/text/pageviewer-idx?c=nietz;cc=nietz;idno=00abf4892m;node=00abf4892m%3A1.11;frm=frameset;view=image;seq=3;page=root;size=s|access-date=12 February 2016|page=200}}</ref>

The process is begun by dividing the left-most digit of the dividend by the divisor.  The quotient (rounded down to an integer) becomes the first digit of the result, and the [[remainder]] is calculated (this step is notated as a subtraction).  This remainder carries forward when the process is repeated on the following digit of the dividend (notated as 'bringing down' the next digit to the remainder).  When all digits have been processed and no remainder is left, the process is complete.

An example is shown below, representing the division of 500 by 4 (with a result of 125).
     <u> <span style="color: red;">1</span><span style="color: green;">2</span><span style="color: blue;">5</span></u>      (Explanations)
    4)500
      <u>4</u>        ( 4 &times;  <span style="color: red;">1</span> =  4)
      <span style="color: darkorange;">1</span>0       ( 5 -  4 =  <span style="color: darkorange;">1</span>)
       <u>8</u>       ( 4 &times;  <span style="color: green;">2</span> =  8)
       <span style="color: darkcyan;">2</span>0      (10 -  8 =  <span style="color: darkcyan;">2</span>)
       <u>20</u>      ( 4 &times;  <span style="color: blue;">5</span> = 20)
        0      (20 - 20 =  0)

[[File:Long division.JPG|thumb|An example of long division performed without a calculator.]]
A more detailed breakdown of the steps goes as follows:

# Find the shortest sequence of digits starting from the left end of the dividend, 500, that the divisor 4 goes into at least once. In this case, this is simply the first digit, 5. The largest number that the divisor 4 can be multiplied by without exceeding 5 is 1, so the digit 1 is put above the 5 to start constructing the quotient.
# Next, the 1 is multiplied by the divisor 4, to obtain the largest whole number that is a multiple of the divisor 4 without exceeding the 5 (4 in this case). This 4 is then placed under and subtracted from the 5 to get the remainder, 1, which is placed under the 4 under the 5. 
# Afterwards, the first as-yet unused digit in the dividend, in this case the first digit 0 after the 5, is copied directly underneath itself and next to the remainder 1, to form the number 10. 
# At this point the process is repeated enough times to reach a stopping point: The largest number by which the divisor 4 can be multiplied without exceeding 10 is 2, so 2 is written above as the second leftmost quotient digit. This 2 is then multiplied by the divisor 4 to get 8, which is the largest multiple of 4 that does not exceed 10; so 8 is written below 10, and the subtraction 10 minus 8 is performed to get the remainder 2, which is placed below the 8. 
# The next digit of the dividend (the last 0 in 500) is copied directly below itself and next to the remainder 2 to form 20. Then the largest number by which the divisor 4 can be multiplied without exceeding 20, which is 5, is placed above as the third leftmost quotient digit. This 5 is multiplied by the divisor 4 to get 20, which is written below and subtracted from the existing 20 to yield the remainder 0, which is then written below the second 20. 
# At this point, since there are no more digits to bring down from the dividend and the last subtraction result was 0, we can be assured that the process finished.

If the last remainder when we ran out of dividend digits had been something other than 0, there would have been two possible courses of action:

# We could just stop there and say that the dividend divided by the divisor is the quotient written at the top with the remainder written at the bottom, and write the answer as the quotient followed by a fraction that is the remainder divided by the divisor.
# We could extend the dividend by writing it as, say, 500.000... and continue the process (using a decimal point in the quotient directly above the decimal point in the dividend), in order to get a decimal answer, as in the following example.

     <u>  31.75</u>     
    4)127.00
      <u>12</u>         (12 ÷ 4 = 3)
       07        (0 [[remainder]], bring down next figure)
        <u>4</u>        (7 ÷ 4 = 1 r 3)                                             
        3.0      (bring down 0 and the decimal point)
        <u>2.8</u>      (7 &times; 4 = 28, 30 ÷ 4 = 7 r 2)
          20     (an additional zero is brought down)
          <u>20</u>     (5 &times; 4 = 20)
           0

In this example, the decimal part of the result is calculated by continuing the process beyond the units digit, "bringing down" zeros as being the decimal part of the dividend.

This example also illustrates that, at the beginning of the process, a step that produces a zero can be omitted.  Since the first digit 1 is less than the divisor 4, the first step is instead performed on the first two digits 12.  Similarly, if the divisor were 13, one would perform the first step on 127 rather than 12 or 1.

===Basic procedure for long division of {{Math|n ÷ m}}===

# Find the location of all decimal points in the dividend {{Mvar|n}} and divisor {{Mvar|m}}.
# If necessary, simplify the long division problem by moving the decimals of the divisor and dividend by the same number of decimal places, to the right (or to the left), so that the decimal of the divisor is to the right of the last digit.
# When doing long division, keep the numbers lined up straight from top to bottom under the tableau.
# After each step, be sure the remainder for that step is less than the divisor. If it is not, there are three possible problems: the multiplication is wrong, the subtraction is wrong, or a greater quotient is needed.
# In the end, the remainder, {{Mvar|r}}, is added to the growing quotient as a [[fraction (mathematics)|fraction]], {{Fraction|r|m}}.

===Invariant property and correctness===
The basic presentation of the steps of the process (above)
focus on the ''what'' steps are to be performed,
rather than the ''properties of those steps'' that ensure the result will be correct
(specifically, that ''q &times; m + r = n'', where ''q'' is the final quotient and ''r'' the final remainder).
A slight variation of presentation requires more writing,
and requires that we change, rather than just update, digits of the quotient,
but can shed more light on ''why'' these steps actually produce the right answer
by allowing evaluation of ''q &times; m + r'' at intermediate points in the process.
This illustrates the key property used in the derivation of the algorithm 
[[#Algorithm for arbitrary base|(below)]].

Specifically, we amend the above basic procedure so that
we fill the space after the digits of the ''quotient'' under construction with 0's, to at least the 1's place,
and include those 0's in the numbers we write below the division bracket.

This lets us maintain an [[Invariant (computer science)|invariant relation]] at every step:
''q &times; m + r = n'', where ''q'' is the partially-constructed quotient (above the division bracket)
and ''r'' the partially-constructed remainder (bottom number below the division bracket).
Note that, initially ''q=0'' and ''r=n'', so this property holds initially;
the process reduces r and increases q with each step,
eventually stopping when ''r<m'' if we seek the answer in quotient + integer remainder form.

Revisiting the ''500 ÷ 4'' example above, we find

     <u> <span style="color: red;">1</span><span style="color: green;">2</span><span style="color: blue;">5</span></u>      (''q'', changes from 000 to <span style="color: red;">100</span> to <span style="color: red;">1</span><span style="color: green;">20</span> to <span style="color: red;">1</span><span style="color: green;">2</span><span style="color: blue;">5</span> as per notes below)
    4)500
      <u>400</u>      (  4 &times; <span style="color: red;">100</span> = 400)
      <span style="color: darkorange;">100</span>      (500 - 400 = <span style="color: darkorange;">100</span>; now ''q=<span style="color: red;">100</span>'', ''r=<span style="color: darkorange;">100</span>''; note ''q&times;4+r = 500''.)
       <u>80</u>      (  4 &times;  <span style="color: green;">20</span> =  80)
       <span style="color: darkcyan;">20</span>      (100 -  80 =  <span style="color: darkcyan;">20</span>; now ''q=<span style="color: red;">1</span><span style="color: green;">20</span>'', ''r=<span style="color: darkcyan;"> 20</span>''; note ''q&times;4+r = 500''.)
       <u>20</u>      (  4 &times;   <span style="color: blue;">5</span> =  20)
        0      ( 20 -  20 =   0; now ''q=<span style="color: red;">1</span><span style="color: green;">2</span><span style="color: blue;">5</span>'', ''r=  0''; note ''q&times;4+r = 500''.)

===Example with multi-digit divisor===

[[Image:LongDivisionAnimated.gif|thumb|right|Animated example of multi-digit long division]]
A divisor of any number of digits can be used. In this example, 1260257 is to be divided by 37. First the problem is set up as follows:

        <u>       </u>
     37)1260257

Digits of the number 1260257 are taken until a number greater than or equal to 37 occurs. So 1 and 12 are less than 37, but 126 is greater. Next, the greatest multiple of 37 less than or equal to 126 is computed. So 3 &times; 37 = 111 < 126, but 4 &times; 37 > 126. The multiple 111 is written underneath the 126 and the 3 is written on the top where the solution will appear:

        <u>  3    </u>
     37)1260257
        111

Note carefully which place-value column these digits are written into. The 3 in the quotient goes in the same column (ten-thousands place) as the 6 in the dividend 1260257, which is the same column as the last digit of 111.

The 111 is then subtracted from the line above, ignoring all digits to the right:

        <u>  3    </u>
     37)1260257
        <u>111</u>
         15

Now the digit from the next smaller place value of the dividend is copied down and appended to the result 15:

        <u>  3    </u>
     37)1260257
        <u>111</u>
         150

The process repeats: the greatest multiple of 37 less than or equal to 150 is subtracted. This is 148 = 4 &times; 37, so a 4 is added to the top as the next quotient digit. Then the result of the subtraction is extended by another digit taken from the dividend:

        <u>  34   </u>
     37)1260257
        <u>111</u>
         150
         <u>148</u>
           22

The greatest multiple of 37 less than or equal to 22 is 0 &times; 37 = 0. Subtracting 0 from 22 gives 22, we often don't write the subtraction step. Instead, we simply take another digit from the dividend:

        <u>  340  </u>
     37)1260257
        <u>111</u>
         150
         <u>148</u>
           225

The process is repeated until 37 divides the last line exactly:

        <u>  34061</u>
     37)1260257
        <u>111</u>
         150
         <u>148</u>
           225
           <u>222</u>
             37

===Mixed mode long division===
For non-decimal currencies (such as the British [[£sd]] system before 1971) and measures (such as [[avoirdupois]]) '''mixed mode''' division must be used.  Consider dividing 50 miles 600 yards into 37 pieces:

           mi -     yd -   ft -   in
       <u>     1 -    634      1      9 r. 15"</u>
     37)   50 -    600 -    0 -    0
           <u>37</u>    <u>22880</u>     <u>66</u>    <u>348</u>
           13    23480     66    348
         <u>1760</u>    <u>222</u>       <u>37</u>    <u>333</u>
        22880     128      <u>29</u>     15
        =====     <u>111</u>     348     <nowiki>==</nowiki>
                   170    <nowiki>===</nowiki>
                   <u>148</u>
                    <u>22</u>
                    66
                    <nowiki>==</nowiki>

Each of the four columns is worked in turn.  Starting with the miles: 50/37 = 1 remainder 13.  No further division is
possible, so perform a long multiplication by 1,760 to convert miles to yards, the result is 22,880 yards.  Carry this to the top of the yards column and add it to the 600 yards in the dividend giving 23,480.  Long division of 23,480 / 37 now proceeds as normal yielding 634 with remainder 22.  The remainder is multiplied by 3 to get feet and carried up to the feet column.  Long division of the feet gives 1 remainder 29 which is then multiplied by twelve to get 348 inches.  Long division continues with the final remainder of 15 inches being shown on the result line.

===Interpretation of decimal results===

When the quotient is not an integer and the division process is extended beyond the decimal point, one of two things can happen:

# The process can terminate, which means that a remainder of 0 is reached; or
# A remainder could be reached that is identical to a previous remainder that occurred after the decimal points were written. In the latter case, continuing the process would be pointless, because from that point onward the same sequence of digits would appear in the quotient over and over. So a bar is drawn over the repeating sequence to indicate that it repeats forever (i.e., [[Repeating decimal#Every rational number is either a terminating or repeating decimal|every rational number is either a terminating or repeating decimal]]).

==Notation in non-English-speaking countries==
{{Multiple issues|section=yes|
{{Unreferenced section|date=March 2019}}
{{Cleanup section|reason=Those blocks aren't doing a very good job of showing off the notation - images would likely be better. Also, using different numbers in the examples reduces emphasis on the notation, which is what's supposed to be on display, so maybe unify that?|date=March 2019}}
{{Globalize section|date=August 2022}}
}}
China, Japan, Korea use the same notation as English-speaking nations including India. Elsewhere, the same general principles are used, but the figures are often arranged differently.

===Latin America===
In [[Latin America]] (except [[Argentina]], [[Bolivia]], [[Mexico]], [[Colombia]], [[Paraguay]], [[Venezuela]], [[Uruguay]] and [[Brazil]]), the calculation is almost exactly the same, but is written down differently as shown below with the same two examples used above. Usually the quotient is written under a bar drawn under the divisor. A long vertical line is sometimes drawn to the right of the calculations.

      500 ÷ 4 =  <span style="color: red;">1</span><span style="color: green;">2</span><span style="color: blue;">5</span>   (Explanations) 
      <u>4</u>                ( 4 &times;  <span style="color: red;">1</span> =  4)
      <span style="color: darkorange;">1</span>0               ( 5 -  4 =  <span style="color: darkorange;">1</span>)
       <u>8</u>               ( 4 &times;  <span style="color: green;">2</span> =  8)
       <span style="color: darkcyan;">2</span>0              (10 -  8 =  <span style="color: darkcyan;">2</span>)
       <u>20</u>              ( 4 &times;  <span style="color: blue;">5</span> = 20)
        0              (20 - 20 =  0)

and

      127 ÷ 4 = 31.75
      <u>124</u>                             
        30      (bring down 0; decimal to quotient)
        <u>28</u>      (7 &times; 4 = 28)
         20     (an additional zero is added)
         <u>20</u>     (5 &times; 4 = 20)
           0
In [[Mexico]], the English-speaking world notation is used, except that only the result of the subtraction is annotated and the calculation is done mentally, as shown below:

     <u> <span style="color: red;">1</span><span style="color: green;">2</span><span style="color: blue;">5</span></u>     (Explanations)
    4)500
      <span style="color: darkorange;">1</span>0      ( 5 -  4 = <span style="color: darkorange;">1</span>)
       <span style="color: darkcyan;">2</span>0     (10 -  8 = <span style="color: darkcyan;">2</span>)
        0     (20 - 20 = 0)

In [[Bolivia]], [[Brazil]], [[Paraguay]], [[Venezuela]], [[French Canadians|French-speaking Canada]], [[Colombia]], and [[Peru]], the European notation (see below) is used, except that the quotient is not separated by a vertical line, as shown below:

     127|<u>4    </u>
    −<u>124</u> 31,75
       30
      −<u>28</u>
        20
       −<u>20</u>
         0

Same procedure applies in [[Mexico]], [[Uruguay]] and [[Argentina]], only the result of the subtraction is annotated and the calculation is done mentally.

===Eurasia===
In Spain, Italy, France, Portugal, Lithuania, Romania, Turkey, Greece, Belgium, Belarus, Ukraine, and Russia, the divisor is to the right of the dividend, and separated by a vertical bar. The division also occurs in the column, but the quotient (result) is written below the divider, and separated by the horizontal line. The same method is used in Iran, Vietnam, and Mongolia.

     127|<u>4    </u>
    −<u>124</u>|31,75
       30
      −<u>28</u>
        20
       −<u>20</u>
         0

In Cyprus, as well as in France, a long vertical bar separates the dividend and subsequent subtractions from the quotient and divisor, as in the [[:fr:Poser une division#Méthode classique|example]] below of 6359 divided by 17, which is 374 with a remainder of 1.

     6359|<u>17    </u>
    −<u>51</u>  |374
     125 |
    −<u>119</u> |
       69|
      −<u>68</u>|
        1|

Decimal numbers are not divided directly, the dividend and divisor are multiplied by a power of ten so that the division involves two whole numbers. Therefore, if one were dividing 12,7 by 0,4 (commas being used instead of decimal points), the dividend and divisor would first be changed to 127 and 4, and then the division would proceed as above.

In [[Austria]], [[Germany]] and [[Switzerland]], the notational form of a normal equation is used. &lt;dividend&gt; : &lt;divisor&gt; = &lt;quotient&gt;, with the colon ":" denoting a binary infix symbol for the division operator (analogous to "/" or "÷"). In these regions the decimal separator is written as a comma. (cf. first section of Latin American countries above, where it's done virtually the same way):

     127 : 4 = 31,75
    −<u>12</u>
      07
      −<u>4</u>
       30
      −<u>28</u>
        20
       −<u>20</u>
         0

The same notation is adopted in [[Denmark]], [[Norway]], [[Bulgaria]], [[North Macedonia]], [[Poland]], [[Croatia]], [[Slovenia]], [[Hungary]], [[Czech Republic]], [[Slovakia]], [[Vietnam]] and in [[Serbia]].

In the [[Netherlands]], the following notation is used:

    12 / 135 \ 11,25
         <u>12</u>
          15
          <u>12</u>
           30
           <u>24</u>
            60
            <u>60</u>
             0

In [[Finland]], the Italian method detailed above was replaced by the Anglo-American one in the 1970s. In the early 2000s, however, some textbooks have adopted the German method as it retains the order between the divisor and the dividend.<ref>Ikäheimo, Hannele: [http://www.opperi.fi/02_opetusvinkkeja/2210_jakolasku.html Jakolaskuun ymmärrystä] (''in Finnish'')</ref>

==Algorithm for arbitrary base ==
{{See also|Division algorithm#Long division}}
Every [[natural number]] <math>n</math> can be uniquely represented in an arbitrary [[number base]] <math>b>1</math> as a [[sequence]] of [[numerical digit|digits]] <math>n=\alpha_{0}\alpha_{1}\alpha_{2}...\alpha_{k-1}</math> where <math>0\leq\alpha_{i}<b</math> for all <math>0\leq i<k</math>, where <math>k</math> is the number of digits in <math>n</math>. The value of <math>n</math> in terms of its digits and the base is
:<math>n=\sum_{i=0}^{k-1}\alpha_{i}b^{k-i-1}</math>
Let <math>n</math> be the dividend and <math>m</math> be the divisor, where <math>l</math> is the number of digits in <math>m</math>. If <math>k < l</math>, then quotient <math>q = 0</math> and remainder <math>r = n</math>. Otherwise, we iterate from <math>0 \leq i \leq k - l</math>, before stopping.

For each [[iteration]] <math>i</math>, let <math>q_{i}</math> be the quotient extracted so far, <math>d_{i}</math> be the intermediate dividend, <math>r_{i}</math> be the intermediate remainder, <math>\alpha_{i}</math> be the next digit of the original dividend, and <math>\beta_{i}</math> be the next digit of the quotient. By definition of digits in base <math>b</math>, <math>0\leq\beta_{i}<b</math>. By definition of remainder, <math>0\leq r_{i}<m</math>. All values are natural numbers. We initiate 
:<math>q_{-1}=0</math>
:<math>r_{-1}=\sum_{i=0}^{l-2}\alpha_{i}b^{l-2-i}</math>
the first <math>l-1</math> digits of <math>n</math>.

With every iteration, the three equations are true:
:<math>d_{i}=br_{i-1}+\alpha_{i+l-1}</math>
:<math>r_{i}=d_{i}-m\beta_{i}=br_{i-1}+\alpha_{i+l-1}-m\beta_{i}</math>
:<math>q_{i}=bq_{i-1}+\beta_{i}</math>
There only exists one such <math>\beta_{i}</math> such that <math>0\leq r_{i}<m</math>.

{{Math proof|title=Proof of existence and uniqueness of <math>\beta_{i}</math>|drop=hidden|proof=
According to the definition of the remainder <math>r_{i}</math>,
:<math>0 \leq r_{i} < m</math>
:<math>0 \leq br_{i-1} + \alpha_{i+l-1} - m \beta_{i} < m</math>
:<math>m \beta_{i} \leq br_{i-1} + \alpha_{i+l-1} < m(\beta_{i}+1)</math>
For the left side of the inequality, we select the largest <math>\beta_{i}</math> such that
:<math>m \beta_{i} \leq br_{i-1} + \alpha_{i+l-1}</math>
There is always a largest such <math>\beta_{i}</math>, because <math>0\leq\beta_{i}<b</math> and if <math>\beta_{i}=0</math>, then
:<math>0 \leq br_{i-1} + \alpha_{i+l-1}</math>
but because <math>b>1</math>, <math>r_{i-1} \geq 0</math>, <math>\alpha_{i+l-1} \geq 0</math>, this is always true. For the right side of the inequality we assume there exists a smallest <math>\beta_{i}^{\prime}</math> such that
:<math>br_{i-1} + \alpha_{i+l-1} < m(\beta_{i}^{\prime} + 1)</math>
Since this is the smallest <math>\beta_{i}^{\prime}</math> that the inequality holds true, this must mean that for <math>\beta_{i}^{\prime}-1</math>
:<math>br_{i-1} + \alpha_{i+l-1} \geq m\beta_{i}^{\prime}</math>
which is exactly the same as the left side of the inequality. Thus, <math>\beta_{i}=\beta_{i}^{\prime}</math>. As <math>\beta_{i}</math> will always exist, so will <math>\beta_{i}^{\prime}</math> equal to <math>\beta_{i}</math>, and there is only one unique <math>\beta_{i}</math> that is valid for the inequality. Thus we have proven the existence and uniqueness of <math>\beta_{i}</math>.
}}
The final quotient is <math>q = q_{k-l}</math> and the final remainder is <math>r = r_{k-l}</math>

===Examples===
In [[Decimal|base 10]], using the example above with <math>n = 1260257</math> and <math>m = 37</math>, the initial values <math>q_{-1} = 0</math> and <math>r_{-1} = 1</math>.

{| class="wikitable" 
|-
! <math>0 \leq i \leq k - l</math>
! <math>\alpha_{i+l-1}</math>
! <math>d_{i} = b r_{i-1} + \alpha_{i+l-1}</math>
! <math>\beta_{i}</math>
! <math>r_{i} = d_{i} - m \beta_{i}</math>
! <math>q_{i} = b q_{i-1} + \beta_{i}</math>
|-
| 0 || 2 || <math>10 \cdot 1 + 2 = 12</math> || 0 || <math>12 - 37 \cdot 0 = 12</math> || <math>10 \cdot 0 + 0 = 0</math> 
|-
| 1 || 6 || <math>10 \cdot 12 + 6 = 126</math> || 3 || <math>126 - 37 \cdot 3 = 15</math> || <math>10 \cdot 0 + 3 = 3</math>
|-
| 2 || 0 || <math>10 \cdot 15 + 0 = 150</math> || 4 || <math>150 - 37 \cdot 4 = 2</math> || <math>10 \cdot 3 + 4 = 34</math> 
|-
| 3 || 2 || <math>10 \cdot 2 + 2 = 22</math> || 0 || <math>22 - 37 \cdot 0 = 22</math> || <math>10 \cdot 34 + 0 = 340</math> 
|-
| 4 || 5 || <math>10 \cdot 22 + 5 = 225</math> || 6 || <math>225 - 37 \cdot 6 = 3</math> || <math>10 \cdot 340 + 6 = 3406</math> 
|-
| 5 || 7 || <math>10 \cdot 3 + 7 = 37</math> || 1 || <math>37 - 37 \cdot 1 = 0</math> || <math>10 \cdot 3406 + 1 = 34061</math> 
|}

Thus, <math>q = 34061</math> and <math>r = 0</math>.

In [[Hexadecimal|base 16]], with <math>n = \text{f412df}</math> and <math>m = 12</math>, the initial values are <math>q_{-1} = 0</math> and <math>r_{-1} = \text{f}</math>.

{| class="wikitable" 
|-
! <math>0 \leq i \leq k - l</math>
! <math>\alpha_{i+l-1}</math>
! <math>d_{i} = b r_{i-1} + \alpha_{i+l-1}</math>
! <math>\beta_{i}</math>
! <math>r_{i} = d_{i} - m \beta_{i}</math>
! <math>q_{i} = b q_{i-1} + \beta_{i}</math>
|-
| 0 || 4 || <math>10 \cdot \text{f} + 4 = \text{f4}</math> || <math>\text{d}</math> || <math>\text{f4} - 12 \cdot \text{d} = \text{a}</math> || <math>10 \cdot 0 + \text{d} = \text{d}</math> 
|-
| 1 || 1 || <math>10 \cdot \text{a} + 1 = \text{a1}</math> || 8 || <math>\text{a1} - 12 \cdot 8 = 11</math> || <math>10 \cdot \text{d} + 8 = \text{d8}</math>
|-
| 2 || 2 || <math>10 \cdot 11 + 2 = 112</math> || <math>\text{f}</math> || <math>112 - 12 \cdot \text{f} = 4</math> || <math>10 \cdot \text{d8} + \text{f} = \text{d8f}</math> 
|-
| 3 || <math>\text{d} = 13</math> || <math>10 \cdot 4 + \text{d} = \text{4d}</math> || 4 || <math>\text{4d} - 12 \cdot 4 = 5</math> || <math>10 \cdot \text{d8f} + 4 = \text{d8f4}</math> 
|-
| 4 || <math>\text{f} = 15</math> || <math>10 \cdot 5 + \text{f} = \text{5f}</math> || 5 || <math>\text{5f} - 12 \cdot 5 = 5</math> || <math>10 \cdot \text{d8f4} + 5 = \text{d8f45}</math> 
|}

Thus, <math>q = \text{d8f45}</math> and <math>r = \text{5}</math>.

If one doesn't have the [[Addition#Table|addition]], subtraction, or [[multiplication table]]s for base {{mvar|b}} memorised, then this algorithm still works if the numbers are converted to [[decimal]] and at the end are converted back to base {{mvar|b}}. For example, with the above example, 
:<math>n = \text{f412df}_{16} = 15 \cdot 16^5 + 4 \cdot 16^4 + 1 \cdot 16^3 + 2 \cdot 16^2 + 13 \cdot 16^1 + 15 \cdot 16^0</math>
and 
:<math>m = \text{12}_{16} = 1 \cdot 16^1 + 2 \cdot 16^0 = 18</math>
with <math>b = 16</math>. The initial values are <math>q_{-1} = 0</math> and <math>r_{-1} = 15</math>.

{| class="wikitable" 
|-
! <math>0 \leq i \leq k - l</math>
! <math>\alpha_{i+l-1}</math>
! <math>d_{i} = b r_{i-1} + \alpha_{i+l-1}</math>
! <math>\beta_{i}</math>
! <math>r_{i} = d_{i} - m \beta_{i}</math>
! <math>q_{i} = b q_{i-1} + \beta_{i}</math>
|-
| 0 || 4 || <math>16 \cdot 15 + 4 = 244</math> || <math>13 = \text{d}</math>  || <math>244 - 18 \cdot 13 = 10</math> || <math>16 \cdot 0 + 13 = 13</math> 
|-
| 1 || 1 || <math>16 \cdot 10 + 1 = 161</math> || 8  || <math>161 - 18 \cdot 8 = 17</math> || <math>16 \cdot 13 + 8</math> 
|-
| 2 || 2 || <math>16 \cdot 17 + 2 = 274</math> || <math>15 = \text{f}</math>  || <math>274 - 18 \cdot 15 = 4</math> || <math>16 \cdot (16 \cdot 13 + 8) + 15 = 16^2 \cdot 13 + 16 \cdot 8 + 15</math> 
|-
| 3 || <math>\text{d} = 13</math> || <math>16 \cdot 4 + 13 = 77</math> || 4 || <math>77 - 18 \cdot 4 = 5</math> || <math>16 \cdot (16^2 \cdot 13 + 16 \cdot 8 + 15) + 4 = 16^3 \cdot 13 + 16^2 \cdot 8 + 16 \cdot 15 + 4</math> 
|-
| 4 || <math>\text{f} = 15</math> || <math>16 \cdot 5 + 15 = 95</math> || 5 || <math>95 - 18 \cdot 5 = 5</math> || <math>16 \cdot (16^3 \cdot 13 + 16^2 \cdot 8 + 16 \cdot 15 + 4 = 16^4 \cdot 13 + 16^3 \cdot 8 + 16^2 \cdot 15 + 16^1 \cdot 4 + 5</math> 
|}
Thus, <math>q = 16^4 \cdot 13 + 16^3 \cdot 8 + 16^2 \cdot 15 + 16^1 \cdot 4 + 5 = \text{d8f45}_{16}</math> and <math>r = 5 = \text{5}_{16}</math>.

This algorithm can be done using the same kind of pencil-and-paper notations as shown in above sections.

        <u>   d8f45</u> r. 5
     12 ) f412df
          <u>ea</u>
           a1
           <u>90</u>
           112
           <u>10e</u>
             4d
             <u>48</u>
              5f
              <u>5a</u>
               5

=== Rational quotients ===
If the quotient is not constrained to be an integer, then the algorithm does not terminate for <math>i>k-l</math>. Instead, if <math>i>k-l</math> then <math>\alpha_{i}=0</math> by definition. If the remainder <math>r_{i}</math> is equal to zero at any iteration, then the quotient is a [[dyadic rational|<math>b</math>-adic fraction]], and is represented as a [[finite decimal]] expansion in base <math>b</math> positional notation. Otherwise, it is still a [[rational number]] but not a <math>b</math>-adic rational, and is instead represented as an infinite [[repeating decimal]] expansion in base <math>b</math> positional notation.

=== Binary division ===
{{main|Division algorithm#Integer division (unsigned) with remainder|Binary number#Division}}

=== Performance ===
On each iteration, the most time-consuming task is to select <math>\beta_{i}</math>. We know that there are <math>b</math> possible values, so we can find <math>\beta_{i}</math> [[Binary search algorithm|using <math>O(\log(b))</math> comparisons]]. Each comparison will require evaluating <math>d_{i}-m\beta_{i}</math>. Let <math>k</math> be the number of digits in the dividend <math>n</math> and <math>l</math> be the number of digits in the divisor <math>m</math>. The number of digits in <math>d_{i} \leq l + 1</math>. The multiplication of <math>m\beta_{i}</math> is therefore <math>O(l)</math>, and likewise the subtraction of <math>d_{i}-m\beta_{i}</math>. Thus it takes <math>O(l\log(b))</math> to select <math>\beta_{i}</math>. The remainder of the algorithm are addition and the digit-shifting of <math>q_{i}</math> and <math>r_{i}</math> to the left one digit, and so takes time <math>O(k)</math> and <math>O(l)</math> in base <math>b</math>, so each iteration takes <math>O(l\log(b) + k + l)</math>, or just <math>O(l\log(b) + k)</math>. For all <math>k - l + 1</math> digits, the algorithm takes time <math>O((k - l + 1)(l\log(b) + k))</math>, or <math>O(kl\log(b) + k^2)</math> in base <math>b</math>.

==Generalizations==
=== Rational numbers ===
Long division of integers can easily be extended to include non-integer dividends, as long as they are [[rational number|rational]]. This is because every rational number has a [[recurring decimal]] expansion. The procedure can also be extended to include divisors which have a finite or terminating [[decimal]] expansion (i.e. [[decimal fraction]]s). In this case the procedure involves multiplying the divisor and dividend by the appropriate power of ten so that the new divisor is an integer&nbsp;– taking advantage of the fact that ''a''&nbsp;÷&nbsp;''b'' = (''ca'')&nbsp;÷&nbsp;(''cb'')&nbsp;–  and then proceeding as above.

===Polynomials===
A generalised version of this method called [[polynomial long division]] is also used for dividing [[polynomial]]s (sometimes using a shorthand version called [[synthetic division]]).

==See also==
* [[Algorism]]
* [[Arbitrary-precision arithmetic]]
* [[Egyptian multiplication and division]]
* [[Elementary arithmetic]]
* [[Fourier division]]
* [[Polynomial long division]]
* [[Short division]]

== References ==
{{reflist}}

==External links==
* [http://www.mathpath.org/Algor/algor.long.div.htm Long Division Algorithm]
* [https://archive.today/20130120232541/http://www.alexpetty.com/2011/05/20/long-division-and-euclids-lemma Long Division and Euclid's Lemma]

{{Number-theoretic algorithms}}

[[Category:Algorithms]]
[[Category:Computer arithmetic algorithms]]
[[Category:Digit-by-digit algorithms]]
[[Category:Division (mathematics)]]