Why long division must either stop or loop

0:00Divide three by eight and something ordinary happens. Nought point three seven five, and then the division is simply over. Now divide five by eleven. Nought point four five four five four five, and it is not going anywhere. Those two digits will alternate for as long as you are willing to keep writing. Two divisions, two completely different endings. The usual question is which fractions do which. The better question is whether there is a third thing a division could possibly do. Could a fraction hand you digits that never stop and never settle into a pattern? Watch the remainders, and the answer turns out to be no.

0:49Here are the same two divisions again, with a second column beside the digits. In that column, the remainder that was left over when each digit was worked out. Three by eight. The remainders run three, six, four. Then the next step lands on nought, and the division has nowhere left to go. Five by eleven. Five, six, five, six. The second remainder is already the last new one there is.

1:20Watch only the digit column and the repetition looks like a coincidence, something the fours and fives happened to fall into. Watch the remainder column and it stops being a coincidence, because the digits are only doing what the remainders make them do. So ask a counting question about that second column. Dividing by seven, what values can a remainder take? It has to be smaller than seven, and it cannot be negative. So the entire supply is nought, one, two, three, four, five, six. Seven values, and that is genuinely all of them.

2:03One of the seven is not like the others. A remainder of nought is the one that ends a division rather than continuing it. So for a division that keeps going, the supply is six. Six values, and the division needs one at every single step, for ever. The whole argument is already sitting there in that sentence. Six containers, and a division that intends to run for ever. Step one takes a remainder. Step two takes a remainder. By the seventh step at the very latest, some container has to be used a second time, because there were only six of them to begin with.

2:48And this is not about sevenths. Divide by any number at all and the supply of remainders that keep a division alive is one fewer than the divisor, so within that many steps one of them has to come round again. Every fraction with a divisor up to four hundred was run. Seventy nine thousand four hundred and one divisions, and not one of them outran its own divisor. The closest was three hundred and eighty nine, which took three hundred and eighty eight steps. One short.

3:25Now the move that turns a repeat into a proof. Look at a single step of the division on its own. What goes in is a remainder. Bring down a nought, divide by the divisor, and what comes out is a digit and the next remainder. And notice what the step never asked for. It did not need the number you started with. It did not need the digits already written. It did not need to know how many steps have gone by.

3:55The remainder and the divisor are the entire input. Everything else is history the division cannot see. Which has a consequence worth being careful about. If two divisions ever arrive at the same remainder under the same divisor, they must produce the same digits from that point on. Not similar. Identical. They are running the same step on the same input. Take every pair of thirteenths and find every remainder they share. A hundred and eighty shared remainders, and at all hundred and eighty the two divisions agree from there on. The same test under seven finds ninety, and those agree too.

4:42So when a single division reaches a remainder it has met before, it is in exactly that situation with itself. Everything after the second arrival has to copy everything after the first. Watch it happen. One divided by seven. The remainders go one, three, two, six, four, five. Every value that keeps a division alive, each used exactly once. And then the next step gives one again. The digits underneath were one, four, two, eight, five, seven. Now that the remainder is back where it began, the digits have no choice but to be as well.

5:27One, four, two, eight, five, seven, and round again. The block is six digits long, and it is six because the remainder cycle is six. The other ending is the same argument with a different landing. A division stops when a remainder of nought turns up, because nought leaves nothing to bring down. Three by eight got there in three steps. Nought is not one more value in the cycle. It is the way out.

5:58So there are exactly two things that can happen to a remainder. It can be nought, and the division stops. Or it can be a value it has already been, and the division loops. Of the divisors from two to a hundred and ninety nine, seventeen give a division that stops, and every other one loops. This also tells you how long a repeating block can possibly get. The block is the remainder cycle, and the cycle cannot be longer than the supply, which is one fewer than the divisor. Dividing by eleven, no block can be longer than ten. Dividing by seven, no longer than six.

6:44That is a limit you can write down from the divisor alone, before doing any dividing whatsoever. A hundred and seventy nine thousand, one hundred and one fractions were measured against it, and none exceeded it. The longest block found anywhere in that range was five hundred and ninety two digits, under a divisor of five hundred and ninety three. Exactly one short, which is the limit being reached rather than merely respected.

7:17Put four divisors side by side and the limit stops looking like a forecast. Eight. The limit is seven, and there is no block at all, because that division stops. Eleven. The limit is ten, and the block is two. Seven. The limit is six, and the block is six. That one uses everything it is allowed. Thirteen. The limit is twelve, and the block is six. Only one of the four reaches its limit. And a bigger divisor plainly does not mean a longer block, because thirteen is the larger number and its block is the same length as seven's, at half of what it is permitted.

8:02Thirteen deserves one more look, because it does something the sevenths never do. Under seven, every numerator from one to six travels the same cycle of remainders. There is one loop and everybody is on it. Under thirteen, the twelve numerators split into two separate cycles of six. One thirteenth runs on the remainders one, three, four, nine, ten and twelve. Two thirteenths runs on two, five, six, seven, eight and eleven, and never once touches the first set.

8:39Four thirteenths is back on the first cycle. Between them the two loops use every remainder from one to twelve, exactly once each. But as two loops, not one, and that is why the block comes out at six rather than twelve. So here is what has actually been shown. Every division either lands on nought and stops, or repeats a remainder and loops. There is no third option, because there is nothing else a remainder is able to do.

9:13A sweep of a hundred and twenty four thousand, two hundred and fifty one fractions found four thousand seven hundred and five that stopped, a hundred and nineteen thousand, five hundred and forty six that looped, and none at all that did neither. Now turn the statement round, which is the direction that earns its keep. If a decimal neither stops nor settles into a repeating block, it cannot have come from a fraction. Not because nobody has found the fraction yet, but because a fraction is incapable of behaving that way.

9:52That is what makes a decimal expansion worth reading slowly. It is not a description of the number. It is a signature.