Long Division and Euclid's Lemma

Most of us learned long division as a way to get an answer, and the remainders were scratch work. You wrote a digit on top, subtracted, brought down a zero, and the small number left at the bottom of each step was something to get past. Do it for one seventh and the digits 142857 appear on top, while the leftovers underneath run 3, 2, 6, 4, 5, 1, and then the whole thing starts over.

The digits are the part we write down, but the remainder is the only thing the next step actually uses. Each step knows the remainder it was handed and nothing else, so when an old remainder comes back, everything after it has to come back too.

That was the part of long division I kept coming back to. I thought of the procedure as unzipping integers. A compact fraction opened into a sequence I could draw, compress, and compare with other sequences. I wanted to know how much structure could come out of such an ordinary calculation.

The early drawings gathered the results. Following the remainders gave me a way to understand how those results were made.

Six steps back to one

Start with a remainder of one and a divisor of seven. Multiply the remainder by ten, take out as many sevens as fit, and keep what is left. Ten contains one seven and leaves three. Thirty contains four sevens and leaves two. Continue the same way.

Remainder in	Digit written	Remainder out
1	1	3
3	4	2
2	2	6
6	8	4
4	5	5
5	7	1

The middle column reads 142857. The last step returns to remainder one, exactly where we began. From there, the calculation must take the same six steps again.

$$\frac17=0.\overline{142857}.$$

The bar marks the repeating block. Nothing in the procedure has to recognize that block as a whole. Each step knows only the current remainder, the divisor, and the base. The repetition follows from returning to the same conditions.

Reading the original worksheet

My early worksheet put many divisions beside one another. The surviving image has nine panels, for dividends one through nine. Each panel runs down a list of divisors.

Its headings need a reading key. Open cycle quotient, labeled $q$, compresses the whole-number part and the nonrepeating decimal prefix by adding their digits until one digit remains. Closed cycle force, labeled $f$, applies the same compression to the shortest repeating block. These were my working labels for two parts of the expansion.

For one fourth, the decimal terminates at .25. Adding two and five gives the seven in the open-cycle column. For one sixth, the first digit is one and the six then repeats. The sheet separates those as an open-cycle value of one and a closed-cycle value of six.

The column labeled remainder can be reproduced by adding the remainders around a complete repeating cycle, then taking that total modulo the divisor. For one third, the only returning remainder is one. For one sixth, it is four. For one seventh, our six remainders add to twenty-one, which leaves zero modulo seven.

Fraction	Open $q$	Remainder $r$	Closed $f$
1/2	5	0	none
1/4	7	0	none
1/3	0	1	3
1/6	1	4	6
1/7	0	0	9
8/7	1	0	9

Here “none” means that there is no repeating tail, shown by a dash in the original. This reading reproduces all seventy-two interior rows, for divisors one through eight. It treats a complete repeating cycle as one object. Its compressed remainder is different from the remainder at an individual step.

For one seventh, the repeating digits add to twenty-seven, then to nine. Eight sevenths has a whole-number part of one and the same repeating tail. Its open value changes to one, while the cycle’s zero and nine remain.

Select the worksheet to inspect all nine panels at full resolution. Most of the examples above are in the upper-left panel. Eight sevenths is in the bottom-middle panel.

The zero and nine endpoint rows

The rows marked alpha and omega retain the original endpoint notation, including infinity symbols and the bracketed values in the last column. They sit outside the interior calculation described above. In the final panel, nine divided by nine puts one in the quotient column.

For ordinary Euclidean division the divisor must be positive. A repeating decimal also has a finite value. One ninth is .111… and nine ninths is one. The endpoint symbols should be read as part of this early drawing’s conventions.

Read across all nine panels

The comparison becomes clearer when we follow the same divisor from panel to panel. These are the closed-cycle values for division by three, six, and seven.

Dividend	Divide by 3	Divide by 6	Divide by 7
1	3	6	9
2	6	3	9
3	none	none	9
4	3	6	9
5	6	3	9
6	none	none	9
7	3	6	none
8	6	3	9
9	none	none	9

The three and six exchange places. In the original, red three and gray six make that reversal visible. At dividends three, six, and nine, both repeating tails disappear. Divisibility explains the gaps. Cancel the factor of three and the denominator is either one or two, giving an integer or a terminating half.

Seven behaves differently. Its repeating blocks are rotations of 142857, all compressing to the blue nine. At dividend seven, the fraction becomes one and the repeating part disappears. It returns at eight.

These were useful comparisons for my early polarity picture. The dividends retaining the red and gray pair are one, two, four, five, seven, and eight. They are also the six positions visited by doubling modulo nine, in the order one, two, four, eight, seven, five. Three and six lie outside that route, along with the zero residue.

Digital-root notation keeps nine for a positive multiple of nine and zero for zero itself. Modulo nine, both belong to the same residue class. That distinction let me retain a seam in the picture even when the arithmetic returned to the same residue.

The colors and signs gave me a way to organize several relationships in one view. Divisibility, digit sums, and returning remainders give us separate calculations to follow through it. The experiment in The Effect of Base on Numeric Fields tested how those relationships changed when decimal was no longer the setting.

Keeping the remainder

Compression also concealed differences. One eleventh repeats 09. Its digits add to nine, and its two remainder states add to eleven. It therefore gives the same three compressed entries as one seventh, zero, zero, and nine. Those entries alone cannot distinguish the two-step cycle from the six-step one.

Following each remainder keeps the missing information. The division lemma gives the precise rule. For a positive divisor $m$, every nonnegative integer $A$ has a unique quotient $Q$ and remainder $r$ satisfying

$$A=mQ+r,\qquad 0\le r<m.$$

Long division applies this rule repeatedly. In decimal, the next dividend is ten times the current remainder. Since the remainder is smaller than the divisor, the new quotient fits into one digit.

There are only $m$ possible remainders. Reaching zero ends the nonzero digits. Returning to a nonzero remainder repeats everything that followed it before. A rational decimal must therefore terminate or eventually repeat.

The remainder also keeps the accounting exact when we stop. After the first three digits of one seventh, we have written .142 and reached remainder six. The full fraction is

$$\frac17=\frac{142}{1000}+\frac6{7000}.$$

The displayed digits alone are an approximation. Together with the retained remainder, they account for the fraction exactly. Division has separated a visible part from something still to be resolved while keeping the whole accounted for. That was part of its appeal for me.

Two remainders, one digit

Even an uncompressed digit can hide a distinction. Divide four and five by thirteen.

$$\begin{aligned} \frac4{13}&=0.\overline{307692},\\ \frac5{13}&=0.\overline{384615}. \end{aligned}$$

Both first digits are three. But forty divided by thirteen leaves one, while fifty leaves eleven. Those different remainders produce different next digits, zero and eight. Agreement at one place does not determine what happens at the next.

In base $b$, with divisor $m$, the two outputs of a long-division step are

$$d=\left\lfloor\frac{br}{m}\right\rfloor,$$

$$r'=br-md.$$

The floor brackets take the whole-number part. The first formula writes the digit. The second retains the state needed to continue. Keeping both makes the calculation available for more than a single decimal expansion.

Digit-Partitioning Primes and the Alignment Formula asks when different remainders remain distinguishable as different digits, and uses that separation to count agreement across a table of fractions. The example with thirteen shows where complete separation begins to fail in decimal.

The later collision work compares digits at specified positions and studies the resulting counts. Carry Boundaries and Bernoulli Spectra develops the floor calculation behind those counts. Digit Collisions and the Cubic Law studies the squared variation of a particular finite carry table as the base grows. Each step needs more information and more argument than a compressed cycle label can supply.

By the end of these early experiments, long division had become a way for me to ask questions of whole families of fractions. I could follow one remainder, compare neighboring rows, or change the base and run the experiment again. The same habit continues in nfield.

The drawings are still good at suggesting which fractions to compare. The comparison itself happens in the remainders, since those are what long division uses at every step, and each digit only shows what the remainder before it has already decided.

First written in March 2011, and rewritten in September 2026 around the original drawings.