Today I'd like to discuss two results that are used much more often than they are proved. A strong understanding of both these theorems is based on notions of linearity. Moreover, the following statements of the two theorems will make it clear that they are essentially the same.

The Chinese Remainder Theorem: Let be pairwise relatively prime positive integers greater than and let be integers. The system of congruences



...


has a unique solution . In particular, it has a unique solution .

The Lagrange Interpolation Theorem: Let be distinct elements of a field and let . The system of polynomial congruences



...


has a unique solution . In particular, it has a unique solution of degree .

(Note that the condition is exactly equivalent to the condition that by the remainder theorem.)

---

Lagrange interpolation is usually stated in a way that is very different from the above; in particular, we usually derive an explicit formula for . Rather than doing so immediately, we will first derive an explicit form for the solution to the problem posed by the Chinese Remainder Theorem; both solutions use the same fundamental idea, which is this:

The operation that takes a polynomial (respectively, an integer) to its values at some distinct points (respectively, its remainders modulo some coprime integers) is linear and invertible.

This suggests the following elegant idea: suppose we could find integers such that




for all . These integers form a basis for the solutions we want in the following sense: the that solves our original system of congruences is

.

This is easily verified by adding together all of the congruences just described. It remains to actually find . But all we have to do is set for some integer and then compute the multiplicative inverse of , which will be equal to . (This is why we need the moduli to be relatively prime.) This can be done using the extended Euclidean algorithm and the resulting answer is unique, hence the resulting is unique. (This does not quite constitute a proof, but I'll let you fill in the details: in terms of the s, what happens if is not unique?)

The exact same ideas work on polynomials: suppose we could find polynomials such that




for all . Then the polynomial we want is

.

Again, this is easily verified by adding together all of the identities (which can be viewed as congruences in the sense described above). Here, though, it is a little more straightforward to compute the polynomials (and this is how Lagrange interpolation is usually stated): if then



where , hence

.

This is exactly analogous to our discussion of multiplicative inverses ; finding a remainder is the same thing as computing . If the form of the Lagrange interpolating polynomials ever seemed mysterious to you, I hope this discussion puts them in the proper context.

Why is computing a remainder so exactly analogous to substituting a value into a polynomial? Well, in one sense it's because polynomial congruences work pretty much the same way as regular congruences, but there has to be something more going on here. When we talk about congruences we are really talking about ideals and quotients with respect to ideals. When we talk about values of a polynomial at points, we are talking about polynomial ideas generated by polynomials of the form ; quotients with respect to those ideals give us values at points. In other words, the question of whether a polynomial has a root at a given point is equivalent to the question of whether it belongs in a given ideal; we are talking algebraic geometry again.

We are not done. I have avoided talking about Lagrange interpolation in the past because it is not, computationally, an efficient way to solve interpolation problems, especially interpolation problems with some additional structure. I have talked about Newton interpolation, which in more general form looks like this: write



where each term has an additional factor. Then





This gives a nice proof both of existence and of uniqueness. (Note the correspondence to the Newton polynomials if .) In linear algebra terms, Lagrange interpolation is equivalent to inverting a Vandermonde matrix (albeit not directly), whereas Newton interpolation is equivalent to inverting a triangular matrix, which is much easier.

The obvious question from here is whether this idea works when applied to CRT. In fact, it does. Write



where again each term has an additional factor. Then





which again provides a nice proof both of existence and of uniqueness. Moreover, I have not seen this proof of CRT before, although it is almost certainly known. Slightly revised, and put into reverse, it provides a proof of the uniqueness of mixed radix representation.

---

So far our discussion of the two theorems has been identical and has fruitfully revealed some interesting ideas. But there is a big advantage in the CRT regime that we don't have in the Lagrange interpolation regime: finiteness. The following can be considered a counting proof, and it begins in the opposite direction as the other.

Let . Define the function that takes to its -tuples of remainders



We claim that this function is injective. Suppose . Then , hence (because of pairwise relative primality), hence in . On the other hand, takes a finite set of size into a Cartesian product of finite sets of size , which has total size . It follows that must be surjective (why?), hence a bijection. The statement that has an inverse is precisely the statement of the Chinese Remainder Theorem.

Of course, the above argument gives no method to explicitly construct the inverse function , but there are important lessons to draw from this proof. In the context of our previous discussion, we took advantage of the fact that was linear (in the appropriate sense) to describe ways to invert it, but if you think about what scalar multiplication really means here, what we're really saying is that is a ring isomorphism. This doesn't directly help us translate this proof to the Lagrange interpolation regime (if we try, the proof looks suspiciously like our earlier ideas), but it does suggest the correct generalization of both results.

---

Practice Problem 1: State and prove the appropriate generalization of both of the main theorems above in a commutative ring in terms of a collection of pairwise relatively prime ideals .

Practice Problem 2 (CRT): a) Show that there exist consecutive composite positive integers for any .

b) (Putnam 1955) Show that there exist consecutive positive integers that are not squarefree for any .

c) Show that there exist consecutive positive integers that cannot be written as the sum of two squares for any .

d) Do there exist positive integers such that for any between and either or ?

Practice Problem 3 (Lagrange interpolation): a) The polynomial of degree satisfies . Compute . (Compare with the solution by Newton interpolation.)

b) Prove the validity of Lagrange interpolation by computing the Vandermonde determinant and showing that it is nonzero. (Hint: the determinant is a homogeneous polynomial in the values. When must this determinant be zero? What degree does the determinant have?)

Practice Problem 4: Give the proof of the uniqueness (and existence) of mixed radix representation I hinted at. (The proof begins like this: given natural numbers and a natural number compute . Now set and compute . Now...)