long division algorithm

Question

Lets say we are running the long division algorithm (this long division algorithm) on two integers $A,B$ and we want to compute $\frac{B}{A}$. Why are we guaranteed to never have to place a digit greater than or equal to $10$ at the top of the division bracket?

Why is this guaranteed to be the case?

An ideal explanation will draw on the fact that we use a base 10 number system.

Answer 1

You can think about the long division algorithm as a bunch of if-else statements. For example, let's say you are dividing $\frac{B}{A}$ where $B$ is some string of digits $\overline{abcd....}$. The long division algorithm for the first digit of the quotient can be thought of as follows:

for digits in B:
\\as digits loops through B, one digit is added at every iteration
\\digits_1 = a, digits_2 = ab, digits_3 = abc, etc.
  if (digits >= A):
    C = digits
    stop loop

Here, for example, if we have $\frac{782458}{984}$, we will get $C = 7824$.

Next, we can do the following:

for i from 1 to 9:
  if (A * i <= C):
   print(1)
  else:
   print(0)
digit_in_quotient = \\last i for which 1 was printed

So, essentially, we are individually testing each digit from $1$ to $9$ to see which one maximises $C - A\cdot i$ given that this difference must be positive.

Now, the crucial part.

There are $2$ cases.

Case $1$: $C$ and $A$ have the same number of digits. In this case, $i$ must be necessarily less than $10$ as $A \cdot 10$ would have an extra digit.

Case $2$: $C$ has $1$ more digit than $A$. In this case, the leading digit of $A$ must be necessarily bigger than $C$ as otherwise, $C$ would have the same digits as $A$. As in case $1$, $i$ must be necessarily less than $10$ as otherwise $A \cdot i > C$ (since the leading digit of $A > $ leading digit of $C$).

As we have seen, in either case, a single-digit will suffice.

This algorithm can now be applied again to find the second digit of the quotient and so on with new values of $C$. Similarly, $A \cdot 10$ will always be greater than $C$. Hence, a digit greater than or equal to $10$ never goes in the quotient.

Edit: In case you didn't realize, the reason $A \cdot i$ cannot be greater than $C$ is because $C - A \cdot i$ would then be negative which is not a possibility in the long division algorithm.

Answer 2

At the first step, even if the first digit of the dividend (5, in the given example) is greater than divisor $d$, the result of the division cannot be greater than 9.

At subsequent steps, you start with a remainder $r$ satisfying $r\le d-1$. Putting a single digit $s$ at its right you get a new number $r'$: $$ r'=10r+s<10(r+1)\le 10d. $$ Hence $r'<10d$ and $r'\div d <10$, so we always get a single-digit result.

Answer 3

This quote from the wikipedia page you link to answers your question.

  ________
37)1261257

Digits of the dividend (1261257) are taken until a number greater than or equal to the divisor (37) occurs. (So 1 and 12 are less than 37, but 126 is greater.)

Then the divisor goes into that sequence at least once. If the divisor went into that sequence 10 or more times then it would have gone into a shorter sequence at least once. (In this example, if you went all the way to 1261 you would have $1261/10 = 126.1 > 37.)

So the digit is at most 9.

---

This is an excellent question. The "standard division algorithm" is opaque. Most teachers would not be able to explain why it produces the correct answer. For a better one, look at exploding dots. You may want to start at the beginning of that sequence of videos to learn a new take on positional notation. It cheerfully allows (in fact, encourages) more than 9 dots in any decimal place.

Answer 4

This is purely because of the way the division algorithm is implemented.

1. Let the dividend have $n$ digits. Consider the first $n$ digits of the divisor. We will call this $X$
2. Find the digit $r$ such that $r \times$dividend $<X$, but $(r+1) \times$dividend $>X$. Multiply the digit and dividend, and find the remainder from $X$.
3. Add 1 more digit from the divisor to the remainder, and repeat step 2 till no more digits are left.

The reason we only ever add 1 digit to the quotient is because of adding only 1 more digit in step 3! The proof is elementary. The remainder is always lesser than $r$, hence the number obtained by adding a digit to its end is always $<10r$, hence the digit we add in quotient is never more than 9. In step 1, since the number we consider has only as many digits as $r$, it is $<10r$ once again.

In fact, if we modified step 1 to take $n+k-1$ digits and step 3 to take $k$ digits each time, we will add upto $k$ digits to the quotient each time. Consider the following example for $k=3$.

We observer that the algorithm concludes faster for a higher $k$, but each individual multiplication is more time-consuming. When doing by hand, it is easier to stick to $k=1$, since we only need to multiply the divisor by a single digit each time.

Answer 5

You can actually divide in such a way that you are not guaranteed such a condition. It's kind of like the normal long division algorithm with a twist.

The picture below shows how typical long division works. All you do is subtract large groupings of the divisor (in this case 6) over and over until you exhaust your dividend (in this case 7,850) and keep track of how many times you subtract (which you do at the top of the division sign).

So normally for 7,850/6, you’d subtract 1000 groups of 6 first, then 300, then 8, and then you’d be done, having only a remainder of 2 left. But other than the training you receive in school, nothing says you HAVE to choose those groups exactly.

Now here’s the interesting part:

If you scroll down further, you will see the same problem with the same answer, calculated with entirely DIFFERENT groupings. The best part is even if you overshoot and use too many groups, you can still use NEGATIVE groups to get back to the answer. It's a much freer and flashy version of long division since there aren't quite so many restrictions. Maybe we can call it Parkour Long Division or something like that.