A MULTIVARIABLE CHINESE REMAINDER THEOREM

Abstract. Using an adaptation of Qin Jiushao’s method from the 13th cen-tury, it is possible to prove that a system of linear modular equations ai1xi + · · · + ainxn = ~bi mod ~mi, i = 1,..., n has integer solutions if mi> 1 are pairwise relatively prime and in each row, at least one matrix element aij is relatively prime to mi. The Chinese remainder theorem is the special case, where A has only one column. 1. The statement with proof Consider a linear system of equations A~x = ~b mod ~m, where A is an integer n × n matrix and ~b, ~m are integer vectors with coefficients mi> 1. Theorem 1.1 (Multivariable CRT). If mi are pairwise relatively prime and in each row, at least one matrix element is relatively prime to mi, then A~x = ~b mod ~m has solutions for all ~b. There is a solution ~x in an n-dimensional parallelepiped X = ZnM/L of volume M = m1 · · ·mn, where L is a lattice in ZnM. Proof. The map φ: x → Ax mod ~m is a group homomorphism from the Abelian group X = Zn to the finite Abelian group Y = Zm1 × · · · × Zmn = Y/L, wher