How to Solve Simultaneous Congruences

Suppose we're trying to solve a set of congruences

x ≡ a_i mod m_i,

where the factors m_i are relatively prime. If we can find a set of numbers G_i that satisfy

G_i ≡ δ_ij mod m_j,

then the solution x can be obtained by adding up appropriate multiples.

x = sum ( a_i G_i )

(I don't know an official name for the numbers G_i, so I used the letter “G” because they remind me of Green's functions.)

The second part is OK, I guess. It explains how to find the numbers G_i, but it does it in prose, by example, and as a result it feels nebulous, like there's nothing there for my mind to grab on to. Nowadays I'd rather see the results in a table, like so, even though there's almost no interaction between the rows.

mi	n/mi	n/mi	vi	Gi
	mod n	mod mi	mod mi	mod n
19	999	11	7	6993
27	703	1	1	703
37	513	32	22	11286

Here (and in An Example) the number n is the product of all the moduli m_i, in this case 18981. The solution x is defined modulo n.

Now let's look at the columns one by one.

1. We already know all about m_i.
2. Since n is the product of all the moduli, n/m_i is the product of all the other moduli. So, although it looks like division, which in group theory is always suspect, it's really just multiplication. (Also, that multiplication of other moduli is the interaction between rows that I was thinking of.)

   We'll use n/m_i to construct G_i and x, so it's appropriate to regard it as a number mod n. And, since it's positive and less than n, it's conveniently pre-normalized into the range [0,n).

3. Next we regard n/m_i as a number mod m_i. It's not necessary to normalize it into the range [0,m_i), but I like to.
4. Next we compute the inverse of n/m_i mod m_i. Let's call that v_i. It's not necessary to normalize it into the range [0,m_i), but the new algorithm does that automatically.
5. Finally, we regard v_i as a number mod n and take the product of columns 2 and 4 to get the Green's function G_i. If v_i was normalized, then the result will be too, since (n/m_i)v_i = n(v_i/m_i).

What about the case where the moduli m_i aren't relatively prime? In practice, I haven't run into it, so I guess it's not particularly useful, but it's easy to understand, so sure, let's take a quick look. The key lies two essays before An Example, in the first paragraph of The Structure of U_n. For each i, we can break the original congruence modulo m_i into congruences modulo the prime power factors of m_i. Then, whenever a prime occurs in more than one congruence, the congruence with the largest exponent will win, and the rest will be either redundant or incompatible. For example, if we know that x ≡ 5 mod 8, then x ≡ 1 mod 4 is redundant but x ≡ 2 mod 4 is incompatible.

New topic! Remember the formula for the solution x?

x = sum ( a_i G_i )

Here's an interesting special case. If the parameters a_i are identically 1, then the solution is just the sum of the Green's functions. However, the solution is also obviously just 1. Therefore, we have the following result.

sum ( G_i ) ≡ 1 mod n

When computing a table, we can use that result either as a shortcut to get the last Green's function or as a checksum at the end.

Here's another interesting special case. If there are three congruences, and the parameters a_i are some permutation of −1, 0, and 1, then the solution is the difference of two Green's functions. Let's consider the six possible permutations and differences all at once. Of the six differences, three are positive, and of the three, the two smallest always add up to the third. The reason for that is easy to understand. If for example G₃ > G₂ > G₁, then

(G₃ − G₁) = (G₃ − G₂) + (G₂ − G₁).

Of course, in modular arithmetic nothing is greater than or less than anything else, and as a result nothing is positive or negative. However, the identity above is still valid, and in fact there are five others just like it that are now equally valid.

Now, here's the strange part. Suppose we normalize the six differences into the range [0,n) and ignore the fact that we shouldn't compare them. The two smallest may not be the same as before, but they still always add up to another difference! Sadly, I don't know any elegant way to prove that. We just have to look at cases, eliminate some, and observe that the rest are covered by the six identities. For example, if G₃ − G₂ is the smallest difference, then G₃ − G₁ can't be the next smallest, because

(G₂ − G₁) = (G₃ − G₁) − (G₃ − G₂) < (G₃ − G₁).

Finally, let's take a quick look at the simultaneous congruences that appeared in the thread Number Maze.

In The Next Block I ran into the second special case, but I solved it with an ad hoc method. For comparison, here's the table of Green's functions for n = 231. As expected, the positive differences are 55, 56, and 111.

mi	n/mi	n/mi	vi	Gi
	mod n	mod mi	mod mi	mod n
3	77	2	2	154
7	33	5	3	99
11	21	10	10	210

In Odds and Ends there were actually two layers of simultaneous congruences. In the first layer there were two instances of the second special case (plus some easier problems). Here's the table of Green's functions for n = 663. As expected, the positive differences are 169, 170, and 339.

mi	n/mi	n/mi	vi	Gi
	mod n	mod mi	mod mi	mod n
3	221	2	2	442
13	51	12	12	612
17	39	5	7	273

And here's the table of Green's functions for n = 665. As expected, the positive differences are 20, 56, and 76.

mi	n/mi	n/mi	vi	Gi
	mod n	mod mi	mod mi	mod n
5	133	3	2	266
7	95	4	2	190
19	35	16	6	210

In the second layer there were a bunch of simultaneous congruences based on the same moduli. They weren't special cases, though, so I was forced to break out the Green's functions. So, the results in this table aren't new.

mi	n/mi	n/mi	vi	Gi
	mod n	mod mi	mod mi	mod n
663	110390	332	2	220780
166	440895	−1	−1	−440895
665	110058	−332	2	220116

Here I left everything unnormalized, partly for consistency with the previous results and partly for clarity. Since n = 73188570, the normalized form of −440895 would be 72747675, a completely unhelpful number.