The Chinese remainder theorem: matching two records

Start with $8$ counters. Groups of $3$ fill $2$ groups and leave $2$ counters. The full groups contain $3\times2=6$ counters; adding the remaining $2$ returns the original $8$. The number left is called the remainder.

Why must the remainder be smaller than a full group? If $3$ counters were still left, we could fill another group, so the grouping would not be finished. The possible remainders after division by $3$ are therefore $0,1,2$. A zero remainder means the groups use every counter.

Each solid box below is a full group; the dashed box holds the remainder. Change the total, then change the group size from $3$ to $5$. Regrouping keeps the total fixed. Green counters belong to full groups; gold counters form the remainder.

Now let $x$ mean the integer we want, and $q$ the number of full groups. “Remainder $2$ after division by $3$” becomes $x=3q+2$. We count whole counters and whole groups, so $x$ and $q$ are integers.

The first record asks for remainder $2$ on division by $3$. Start at $2$ and add a full group of $3$ each time. The remainder stays unchanged, giving $2,5,8,11,14,17,\ldots$. These are all the nonnegative possibilities for the first record: after removing the two leftover counters, only whole groups of three may remain.

For the second record, start at $3$ and add $5$ at a time, giving $3,8,13,18,23,\ldots$. We need a number appearing in both lists. Adding the two remainders is not the operation we need.

Each step below checks one candidate from the first list, then groups that same total in fives. Vertically aligned numbers in the two rows refer to the same total. A filled mark means the corresponding record is satisfied. Check $2$, then $5$, then $8$.

Check $8$ against both records: $8=3\times2+2$ and $8=5\times1+3$. It works. But is it the only answer? Next, we need a way to account for every possibility.

Adding $15$ to a total adds five full groups of three, or three full groups of five, because $15=3\times5=5\times3$. Either grouping gains only full groups, so neither remainder changes. Subtracting $15$ preserves the remainders too.

Every integer can be divided by $15$ to give $x=15t+r$, with $0\le r<15$. Here $t$ is an integer and $r$ is the remainder. For example, $23=15\times1+8$, while $-7=15\times(-1)+8$. Adding or subtracting multiples of $15$ therefore brings any integer into the interval from $0$ to $14$.

So checking $0$ through $14$ cannot miss an entire family of answers. The first record leaves only $2,5,8,11,14$ in that interval. Their remainders on division by $5$ are $2,0,3,1,4$ respectively. Only $8$ leaves $3$. Hence every integer answer is $x=8+15t$, where $t$ is any integer.

For the original pile of counters, a total cannot be negative, so we retain $8,23,38,\ldots$. For an integer problem, the full family extends in both directions: $\ldots,-22,-7,8,23,38,\ldots$.

We can shorten the record with $x\equiv2\pmod3$, read as “$x$ is congruent to $2$ modulo $3$”. Here it says exactly that division by $3$ leaves $2$, or that $x-2$ is an integer multiple of $3$. The grouping number, $3$, is called the modulus.

We have completely solved the example with $3$ and $5$. Why do some other pairs of grouping numbers always give an answer, while others may fail? We need to examine the common factors of the two group sizes.

A positive integer dividing both numbers without a remainder is a common factor. The greatest one is their greatest common divisor, written $\gcd(m,n)$. For example, the common factors of $4$ and $6$ are $1,2$, so the greatest is $2$. The only common factor of $3$ and $5$ is $1$; such a pair is called coprime.

How can we find the greatest common divisor and connect it to the original numbers? Divide with remainder: $a=bq+r$. A divisor of both $a$ and $b$ also divides $r=a-bq$. Conversely, a divisor of $b$ and $r$ also divides $a=bq+r$. Thus the pairs $(a,b)$ and $(b,r)$ have exactly the same common divisors.

Replace each pair by its divisor and remainder. Positive remainders strictly decrease, so eventually the remainder is zero. Every positive integer divides zero, so the last pair has greatest common divisor equal to its nonzero entry. That entry may be an earlier remainder, or the original divisor itself: for $6=2\times3+0$, the last pair is $(3,0)$ and the answer is $3$. Each replacement preserved all common divisors, so this nonzero entry is also the original greatest common divisor. This procedure is the Euclidean algorithm.

Below, retain the original $3$ and $5$ while writing each new remainder as integer multiples of those two numbers added together. The first line is just $3=0\times5+3$: starting with the smaller number is permitted, and the following steps still work.

Now apply the tool to any coprime positive moduli $m,n$. Their greatest common divisor is $1$, so Euclidean division and substitution give integers $u,v$ with $um+vn=1$. These are the two coefficients of a combination like the one above; either may be negative.

We want an integer $x$ leaving remainder $a$ on division by $m$, and remainder $b$ on division by $n$, with $0\le a<m$ and $0\le b<n$. First ensure the first record by putting $x=a+mk$, with integer $k$ still to be chosen. Whatever $k$ is, $x-a$ is a multiple of $m$.

The second record asks for $x-b=a-b+mk$ to be a multiple of $n$. We therefore want the difference between $mk$ and $b-a$ to be divisible by $n$. Multiply the known equation $um+vn=1$ by $b-a$ to make this difference:

Choose $k=u(b-a)$. The preceding equation then gives $mk-(b-a)=-nv(b-a)$, a multiple of $n$. Therefore $x=a+mu(b-a)$ meets both records. This proves existence for every allowed pair of remainders, rather than only for the examples we tried.

Next, how many different families of answers can there be? If $x,y$ both satisfy the records, their difference is divisible by both $m$ and $n$. First write $x-y=mt$. We know that $n$ divides $mt$ and need to show that it divides $t$; we cannot just erase $m$ without a reason.

Multiply $um+vn=1$ by $t$ to get $t=u(mt)+v(nt)$. The first term is a multiple of $n$ because $mt$ is. The second is also a multiple of $n$ because it contains a factor of $n$. Their sum is a multiple of $n$, so $t=ns$ for some integer $s$. Thus $x-y=mns$.

Any two answers therefore differ by a multiple of $mn$. Conversely, adding any multiple of $mn$ to an answer preserves both remainders. Divide a known answer by $mn$ and keep its remainder $r$: it is the unique answer with $0\le r<mn$, and all answers are $x=r+mn s$. This is the Chinese remainder theorem for two coprime moduli.

What if the moduli are not coprime? Numbers leaving remainder $1$ on division by $4$ are odd; numbers leaving remainder $2$ on division by $6$ are even. An integer cannot be both, so these records conflict. Their common factor $2$ is where the conflict occurs.

Let $d$ be the greatest common divisor of the two moduli. A common answer would have $x=a+mk=b+nl$. Rearranging gives $b-a=mk-nl$. Since $d$ divides both $m,n$, each term on the right is a multiple of $d$. Therefore $b-a$ must be divisible by $d$. This is a necessary condition.

The condition is also sufficient. Euclidean division gives $um+vn=d$. If $b-a=dc$, multiply by the integer $c$ to get $muc+nvc=b-a$. Choose $x=a+muc$. Its difference from $a$ is a multiple of $m$, and its difference from $b$ is $-nvc$, a multiple of $n$. Both records are satisfied.

Now find the exact repetition interval. Write $m=dM$ and $n=dN$ by removing the common factor. $M,N$ must be coprime: a common factor $h>1$ would make $dh$ a common divisor of $m,n$ larger than $d$, contradicting the choice of greatest common divisor.

The difference of two answers is a multiple of $m$, say $dMt$. It is also a multiple of $n=dN$, so $Mt$ is a multiple of $N$. Since $M,N$ are coprime, the cancellation argument proved in the preceding chapter says that $t$ is a multiple of $N$. The difference of answers is therefore a multiple of $dMN=mn/d$.

$dMN$ is itself a multiple of both $m=dM$ and $n=dN$. The same argument shows that every common multiple must be a multiple of it. It is therefore their least common multiple, written $\operatorname{lcm}(m,n)$. When answers exist, they repeat at precisely this interval.

Change the moduli and remainders below. Whether the difference of remainders is divisible by the greatest common divisor tells us whether an answer can exist. You can check this by inspecting the candidates. The table includes every candidate meeting the first record in one full repetition interval, so completing the table completes the check for these inputs.

Combining two records gives another remainder record. For example, $x=8+15t$ can be written $x\equiv8\pmod{15}$. If we also require remainder $2$ on division by $7$, combine that new record with the one we have just obtained.

Inspect $8,23,38,53,68,83,98$. Their remainders on division by $7$ are $1,2,3,4,5,6,0$, so we select $23$. Because $15$ and $7$ are coprime, the new period is $15\times7=105$, giving $x=23+105s$. Check all original records: $23=3\times7+2$, $23=5\times4+3$, and $23=7\times3+2$.

With more records, repeat this combination. At each stage, check the greatest-common-divisor condition for the two current moduli. A conflict means no integer satisfies all records. Otherwise, the combined record retains all earlier conditions, ready for the next one.

If the original moduli are pairwise coprime, combining preserves the needed coprimality. To see why, suppose $p$ is coprime to both $m$ and $n$. We have $um+vp=1$ and $rn+sp=1$. Multiplying gives $1=urmn+p(ums+vrn+vsp)$, so any common divisor of $mn$ and $p$ must divide $1$. Repeating this argument gives the Chinese remainder theorem for more coprime moduli.