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
$\endgroup$ 04 Answers
$\begingroup$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.
$\endgroup$ 4 $\begingroup$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).
$\endgroup$ 5 $\begingroup$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.
But, you ask, what about remainders?
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$.
$\endgroup$ 1 $\begingroup$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.
$\endgroup$
