The Collision Invariant

Divide 4 by 13. Then divide 5 by 13.

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

Both begin with a 3. Long division produces that digit from two different remainders, 4 and 5. They occupy the same digit bin.

Now multiply the remainder 5 by 6.

$$6\times5=30=2\times13+4.$$

After division by 13, the remainder is 4. Multiplication has moved us from one remainder to another, but the next digit is still 3. I call this a collision.

Do the same thing to every nonzero remainder. Multiplication by 6 gives two collisions. Multiplication by 11 also gives two. Every other multiplier except 1 gives none.

Multiplier	2	3	4	5	6	7	8	9	10	11	12
Collisions	0	0	0	0	2	0	0	0	0	2	0

Nine zeros. At 29 there are nine too. At every prime larger than ten, exactly nine multipliers move every remainder out of its digit bin. The other collision counts change with the prime. This count does not.

The question that interests me is how a rule this simple can keep giving the same answer while the number of remainders grows. Four finite results fit together around that question. They describe the multipliers that give no matches, the part of the count that repeats, and the symmetry inside it.

Keeping the groups, changing the labels

The digit function writes the long-division step in one expression,

$$\delta(r)=\left\lfloor\frac{br}{p}\right\rfloor.$$

Here $b$ is the base and $p$ the denominator. The floor means round down. In base ten with denominator 13, the remainders 4 and 5 both give 3 because $40/13$ and $50/13$ both lie between 3 and 4.

Multiply each remainder by ten and keep its remainder modulo 13. Our pair becomes

$$4\longmapsto1,\qquad 5\longmapsto11.$$

The two new labels have the same final digit. This happens throughout the partition. Each digit bin becomes a group of numbers with the same remainder upon division by ten.

The bin numbered 3 has become the class ending in 1. The groups are preserved, though their names change. This distinction is useful. We can forget the interval boundaries and compare remainders modulo the base instead.

I call this the linearization. It works because long division gives the exact identity $br=p\delta(r)+x$, where $x$ is the new remainder. Modulo $b$, this says $x\equiv-p\delta(r)$. Since $p$ and $b$ have no common factor, different digits produce different classes.

The collision count is now a congruence count. Multiply a new label $x$ by $g$, reduce modulo $p$, and ask whether its remainder modulo $b$ changed.

The nine multipliers

The linearization gives the entire zero set,

$$g\equiv-\frac{u}{b-u}\pmod p.$$

Take $u=1,\ldots,b-1$.

Division here means modular division. To divide by $b-u$, multiply by the number that makes $b-u$ equal to 1 modulo $p$. That number exists because $p>b$.

For base ten and $p=13$, choosing $u=1$ gives $-1/9\equiv10$. Indeed, $9\times10\equiv-1$ modulo 13. Choosing $u=5$ gives $-5/5=-1\equiv12$. Both multipliers appear among the zeros in the opening table.

There are nine distinct answers as $u$ runs from 1 to 9. At another prime, the same nine fractions give a different list of multipliers. The proof shows that this list is complete.

This is the gate width theorem. In every base $b\geq2$, every prime $p>b$ has exactly $b-1$ such multipliers. The base need not generate every nonzero remainder. Short repeating cycles and long ones are all included.

The complement multiplier $-1$ has a familiar explanation in an even base. It replaces each digit $d$ by $b-1-d$. No digit equals its own complement, so no digit survives. In the rational family it is the middle choice $u=b/2$.

Ten more collisions

Fix the multiplier at the base itself. In decimal notation, multiplication by ten advances the long division by one position. We count the remainders whose next two digits agree.

For denominator 109, there are 18. Subtract $\lfloor108/10\rfloor=10$, the smaller digit-bin size, and the difference is 8.

For denominator 409, there are 48. Subtract 40. Again 8.

Denominator $N$	Collisions $C_N(10)$	Baseline $\lfloor(N-1)/10\rfloor$	Difference
109	18	10	8
209	28	20	8
409	48	40	8
1009	108	100	8

I have included 209 deliberately. It is $11\times19$, and it follows the same rule. The count uses all the nonzero remainders, including those that have a factor in common with the denominator.

The signed difference is the collision invariant,

$$S(N)=C_N(b)-\left\lfloor\frac{N-1}{b}\right\rfloor.$$

The baseline records the scale of a digit bin. It is not the exact average over multipliers.

To see why the difference repeats, divide the interval from 0 to 1 into a hundred equal pieces. Label them 00 through 99. A fraction in piece 37 begins with the digits 37. Its first two digits agree precisely when it falls in one of the ten pieces 00, 11, 22, and so on through 99.

When a denominator coprime to ten increases by 100, each piece gains one remainder. Each of the ten selected pieces contributes one more collision. The subtraction removes exactly those ten additions. Only the last two digits of the denominator are left in the answer.

This is finite determination. For $N>100$ coprime to ten, $S(N)$ depends only on $N\bmod100$. The forty eligible endings make the collision periodic table.

Two digits are necessary. Endings 01 and 91 have the same last digit, but their invariant values are 0 and $-9$. No rule that reads just that final digit can distinguish them.

At lag $\ell$, we compare digits $\ell$ positions apart. The determining modulus is $b^{\ell+1}$, so the final $\ell+1$ base-$b$ digits suffice when $N>b^{\ell+1}$ and $N$ is coprime to $b$. The proof supplies a pair of classes at every base and lag that agree in their last $\ell$ digits but give different values. The last digit we add is doing necessary work.

The partner of 09

The class ending in 09 gives $+8$. Its partner, 91, gives $-9$. They add to $-1$.

The same relation holds throughout the table,

Ending $a$	$S(a)$	Ending $100-a$	$S(100-a)$	Sum
01	0	99	$-1$	$-1$
03	2	97	$-3$	$-1$
09	8	91	$-9$	$-1$
17	1	83	$-2$	$-1$

There are twenty pairs. Each contributes $-1$, so the forty entries total $-20$. Their average is exactly $-1/2$.

The reflection identity holds in every base and at every lag. With $m=b^{\ell+1}$, it reads

$$S_\ell(a)+S_\ell(m-a)=-1.$$

The average here is over the finite table. There is no question about how often primes visit its classes in this calculation. Pairing the entries is enough.

A crossing and its reflection

Inside the table formula are small yes-or-no counts. At the decimal piece 11, for instance, we ask whether the step from $11a$ to $12a$ crosses a multiple of 100.

For $a=9$, the step goes from 99 to 108. It crosses 100. For the partner $a=91$, it goes from 1001 to 1092. It stays below 1100.

Among the forty eligible endings, exactly twenty cross and twenty do not. Replace piece 11 by any interior piece from 01 to 98 and the split is still twenty and twenty. The members of each group can change. Its size cannot.

This is the half-group law. It holds among the residue classes coprime to any modulus $m\geq3$, with no requirement that $m$ be a power of a base. Reflection pairs a crossing with a noncrossing. The first and last pieces are excluded because their steps never cross and always cross, respectively. Keeping those two endpoints in the full collision count gives the offset $-1$ in the reflection identity.

I like that the balance can be inspected at both scales. The table pairs whole invariant values. The half-group law pairs the individual crossings from which those values are built. The same reflection is visible in each.

We began with two fractions whose first digit was 3. Following that agreement through multiplication gives a zero set, a finite table and an exact balance within the table. A denominator can grow without bound while its collision deviation stays fixed. The reason is in the count itself. Every complete block adds the same amount to the collisions and to the baseline. What distinguishes one ending from another is the part of the count that the complete blocks cannot change.