Chinese Remainder Theorem

Given a system with \( a_i, n_i \in Z \):

\begin{align*} &x \equiv a_1 \pmod{n_1} \\ &x \equiv a_2 \pmod{n_2} \\ &... \\ &x \equiv a_k \pmod{n_j} \end{align*}

If \( n_j \) are pairwise coprime, then the Chinese Remainder Theorem asserts that the system has a unique solution modulo \( N = n_1 * n_2 * ... * n_j \).

A proof can be found here.

They can also be solved in sympy.

Note if we are given \( a \equiv b \pmod{n} \), and \( \{q_1 ... q_k \} \) is some pairwise coprime set whose product is \( n \) then the Chinese Remainder Theorem asserts that:

\[ a \equiv b \pmod{n} \iff a \equiv b \pmod{q_i} \ \forall i = 1...k \]

ie \( x \equiv 7 \pmod{30} \iff x \equiv 7 \pmod{3}, \ x \equiv 7 \pmod{5}, \ x \equiv 7 \pmod{2} \)

There exist an arbitrarily large number of consecutive integers, none of which is squarefree.

Let \( \{p_1 \ ... \ p_n\} \) be the set of the first \( n \) primes. Then the statement true if a solution exists for the set of simultaneous congruences:

\begin{align*} x &\equiv 0 \pmod{p_1^2} \\ x + 1 &\equiv 0 \pmod{p_2^2}\\ ... \\ x + (n - 1) &\equiv 0 \pmod{p_n^2} \end{align*}

ie

\begin{align*} x &\equiv 0 \pmod{p_1^2} \\ x &\equiv -1 \pmod{p_2^2}\\ ... \\ x &\equiv -n + 1 \pmod{p_n^2} \end{align*}

Of which a unique solution is guarenteed by the Chinese Remainder Theorem.

If \( n_i \) are not pairwise coprime, it is still possible to apply CRT. Suppose that:

\[ x \equiv a \pmod n \]

Now we prove:

\[ (1)\ x \equiv a \pmod n \iff \forall k \in U, x \equiv a \pmod k \]

where

\[ U = \{ N^p : N \text{ prime },\ N | n,\ N^{p + 1} \not{|} n \} \]

ie \( U \) is the prime number decomposition of \( n \).

The forward case is trivial:

\begin{align} &x \equiv a \pmod n \nonumber \\ \Rightarrow& \exists \lambda \in Z \ s.t. \ x - a = \lambda n \nonumber \end{align}

Now applying modulo \( k \), since \( k | n \):

\[ \Rightarrow& x - a \equiv 0 \pmod{k} \]

For the backward case, note that the distinct elements of \( U \) form the prime decomposition of \( n \), hence their product is \( n \). All of the distinct elements are also coprime. Consider the system \( S \):

\begin{align*} &x \equiv a \pmod{k_1}\\ &x \equiv a \pmod{k_2}\\ &...\\ &x \equiv a \pmod{k_i} \end{align*}

where \( k_1, k_2, ... k_i \) are the distinct elements of \( U \). Then by standard CRT there exists a unique solution modulo \( k_1*k_2*...*k_i = n \). From inspection, we can identify the trivial solution \( x = a \), and thus by CRT this is the unique solution modulo \( n \). Hence the solution set of \( S \) is identical to the solution set of:

\[ x \equiv a \pmod n \]

Hence (1) is proved. Suppose we have some system of linear congruences which satisfy the predicates required by CRT except there is some pair of congruences whose moduli are not coprime:

\[ x \equiv a_1 \pmod{k_1} \] \[ x \equiv a_2 \pmod{k_2} \]

Then by (1), we can reduce these two congruences into more congruences, whose moduli are either pairwise coprime or of the form:

\[ x \equiv a \pmod{a^{p_1}} \] \[ x \equiv b \pmod{a^{p_2}} \]

Which has solutions \( \iff a = b \), in which case we can ignore the congruence with the smaller power. With these two reductions, we now have a system of congruences which we can apply CRT to.