# Long Division Algorithm Proof

As I was doing my homework today, a sudden thought popped into my head. Why does our long-division algorithm work and how can I prove it? Why does it the function the way it does? Why do we not do division starting from the right and going to the left?

Thanks

So instead of dividing using long division lets instead just subtract off multiples until we get one that too small and count how many times we do it. So for example if I'm dividing $$17$$ by $$3$$ I would calculate $$17-3=14$$ and set my count to $$1$$. I would repeat this again and again with $$14-3=11$$ and setting the count to two. Counting in this fashion when the count is set to $$5$$ we are left with $$2$$ and low and behold $$3\cdot5 + 2 =17$$ and we have division with remainder.

But this becomes impracticable quickly. Maybe we're trying to divide $$9843$$ by $$7$$ and subtracting off each $$7$$ one at a time would be tedious and time consuming. So, instead we subtract them off in groups of $$70$$ and increase the counter by $$10$$ each time instead. In fact, we can do even better and subtract of $$7000$$ to start, and increase the counter by $$1000$$ then work on the smaller problem.

So finally we ask this question - what's the best way to group the $$7$$s so that they do the most work and I have to do the least steps? Ideally we want to find the biggest multiple of $$7$$ that is smaller than $$9843$$, subtract that off, add the number of multiples to the counter, then continue with the smaller sub-problem, repeating at each stage.

And now that we're subtracting in the most efficient way, digit by digit, we finally realize we're just doing the division algorithm as usual now. Given how tedious long division can be the method does reduce the work. You can structure your proof around this idea of subtracting and grouping so I'll leave you the pleasure of reconstructing the result for yourself.

• But what about division of smaller number by larger number? This logic won't work in this case. Feb 7, 2022 at 14:34
• @user161005 right, because you're already done and don't have to do any more work. The smaller number is the remainder and there is no quotient. Done. Feb 7, 2022 at 15:31
• Sorry, I mean, there is "Long division with decimals" algorithm, which allows to find decimal for division of small number by big number. And such variation of long division isn't covered in your post Feb 7, 2022 at 16:38
• @user161005 Decimals are not used in higher mathematics. That's more of a science and engineering thing where they want an approximation to so many digits. In that case too the algorithm terminates after a finite length of time and is reducible to an integer long division problem by multiplying then dividing by some appropriate power of ten. Note that at every step you still have a quotient and still have a remainder when the algorithm is extended this way. Feb 7, 2022 at 18:55

Decimal integer long division algorithm  Write the dividend as $$\, n = a \,10^{\large k}\! +b \,$$ where $$\, a> d =$$ divisor. Divide $$\,a\,$$ by $$\,d$$ $$\rightarrow \color{#c00}{ a = q\,d + r}.\$$ Then

$$\dfrac{n}d\ =\ \dfrac{\color{#c00}a\,10^{\large k} + b}d\ =\ \dfrac{(\color{#c00}{qd+r})10^{\large k} + b}{d}\ =\ \color{#c00}q\, 10^{\large k} +\!\!\! \underbrace{\dfrac{\color{#c00}r10^{\large k}+b}d}_{\large\rm \color{#0a0}{recurse}\ on\ this}$$

Next $$\rm\color{#0a0}{recursively}$$ apply the algorithm to the indicate fraction (with smaller numerator).

Usually we choose $$a$$ minimal, but we can choose any value of $$\,a>d\,$$ (it may simplify division)

Scaling by powers of $$10$$ allows us to reduce any division of decimals to the above integer case (this is implicit in the usual tabular implementation of the algorithm).

• This is too short, IMHO. What do all (except n and d) these letters mean? Why do we need "+b" in the equation of the dividend, while a*10^k already can express any number? Feb 7, 2022 at 14:47
• Also it's unclear about what values all these letters can take. Feb 7, 2022 at 14:48
• @user161005 For clarity I present the grade school long division algorithm for naturals in radix $10$ (decimal notation). Arbitrary decimals can be handled this way by shifting as need be (scaling by powers of $10$ ). Compare to the (long) polynomial division algorithm. Feb 7, 2022 at 17:26
• Alas, but I don't see how it answers my questions. And I'm already aware that this is long division from arithmetics, not polynomial long division from algebra. Feb 7, 2022 at 17:39
• @user161005 "for naturals" means that all the variables are naturals. The remainder "$+b$" is needed because not every natural has the form $a10^k$. Here $\color{#c00}a$ is a leading chunk of the decimal digits of $n$ that is greater than the divisor $d$ (but small enough to make that the division $a\div d$ easy). The "compare" remark is emphasize similarity in both division algorithms. Feb 7, 2022 at 18:09

Because multiplication is distributive over addition.

$$(m+a) d = md + ad$$

So if $$dx = k + m$$ we can solve $$x = \frac {k+m}d = \frac kd + \frac md$$

So to figure out $$\frac Nd$$ is to solve $$dx = N$$ and if we have $$N= 10*M + N'$$ than we have to solve $$x = \frac {10*M + N'}d = \frac {10*M}d + \frac {N'}d$$ if it is easier.

For and $$M$$ you have $$M = q*d + r$$ for some remainder.

So if $$N = 10M + N'$$ and $$M = q*d + r$$

$$N = 10M + N' = 10(q*d + r) + N'$$ so

$$\frac Nd = 10q + \frac {(10r + N')}d$$

And $$10r + N'$$ must *also have something in that form where $$10r_1 + N' = vd + s$$

So $$N = 10M + N'=$$

$$10(q*d + r) + N'=$$

$$10q*d + (10r + N')=$$

$$10q*d + v*d + s$$ so

$$\frac Nd = \frac {10q*d + v*d + s}d = \frac {10q*d}d + \frac {vd}d + \frac sd = 10q + v + \frac sd$$.

• Solid Answer man, thanks! Dec 18, 2018 at 1:52

Long division works, because you are subtracting multiples of the divisor.

Square roots are a form of long division, for which the divisor changes. In this case, we suppose a^2 has already been subtracted, and the next divisor is 20a+_. When we put b, this is the difference between the squares of 10a+b and 10a.

Modified forms of the algorithm allow one to handle large bases, like 120.