Solving multiple congruences by CRT = Chinese Remainder Theorem

Solution 1:

As explained below, any solution $\,x\equiv a\pmod{\!M}\,$ computed by some CRT algorithm is necessarily unique $\!\bmod M = $ lcm of the moduli. But a CRT algorithm (or formula) need not always return the least nonnegative solution, so we will need to reduce it $\!\bmod M\,$ if we seek that. In your case $\,31264\bmod 5005 \equiv 1234,\,$ where $\,M = 5005 = {\rm lcm}(5,7,11,13)$.

Here is a much simpler way to immediately obtain the sought answer. Contrast the solution below to the much longer solution in your link, which involves calculations with much larger numbers and performs $4$ inversions vs. the single simple inversion below. Always search for hidden innate structure in a problem before diving head-first into brute-force mechanical calculations!

Key Idea $ $ the congruences split into pairs with obvious constant solutions by CCRT, viz.

$$\begin{align}&\rm x\equiv \ \ \ 2\ \ (mod\,\ 7),\ \ x\equiv \ \ \ 2\ \ \:(mod\ \,11) \iff\ x\equiv \ \ \ \color{#0a0}2\ \ (mod\,\ \color{#0a0}{77})\\[0.3em] &\rm x\equiv -1\ \ (mod\,\ 5),\,\ x\equiv\ {-}1\ \ (mod\,\ 13) \iff\ x\equiv \color{#c00}{-1}\ \ (mod\,\ \color{#c00}{65})\end{align}\qquad$$

So we reduced the above four original LHS equations to the above two RHS equations, which are easy to solve by CRT = Chinese Remainder Theorem. $ $ Indeed, applying Easy CRT below

$\rm\quad\quad\quad\quad\quad x\equiv\ \color{#0a0}{2 + 77}\ \bigg[\displaystyle\frac{\color{#c00}{-1}-\color{#0a0}2}{\color{#0a0}{77}}\ mod\,\, \color{#c00}{65}\bigg]\,\ \ (mod\ 77\cdot65)$

In brackets: $\ \rm\displaystyle\left[\, mod\ \ 65\!:\ \ \frac{\color{#c00}{-1}-\color{#0a0}2}{\color{#0a0}{77}} \equiv \frac{-3}{12} \equiv \frac{-1}4 \equiv \frac{64}4 \equiv \color{#d0f}{16}\,\right]\ \ \ $ (see Beware below)

therefore $\rm\ \ x\ \equiv\ \color{#0a0}{2 + 77}\,[\,\color{#d0f}{16}\,] \equiv 1234\ [\equiv 31264]\,\ \ (mod\ 77\cdot 65)\quad $ QED

Theorem $\:$ (Easy CRT) $\rm\ \ $ If $\rm\ m,\:n\:$ are coprime integers then $\rm\ m^{-1}\ $ exists $\rm\ (mod\ n)\ \ $ and

$\rm\displaystyle\qquad\quad\quad\quad \begin{eqnarray}\rm x&\equiv&\!\rm\ a\ \ (mod\ m) \\ \rm x&\equiv&\!\rm\ b\ \ (mod\ n)\end{eqnarray} \ \iff\ \ x \equiv\, a + m\ \bigg[\frac{b-a}{m}\ mod\ n\,\bigg]\,\ \ (mod\ m\:\!n)$

Proof $\rm\ (\Leftarrow)\ \ \ mod\ m\!:\,\ x \equiv a + m\ [\,\cdots\,] \equiv a,\ $ and $\rm\ mod\ n\!:\,\ x \equiv a + (b\!-\!a)\ m/m \equiv b$

$\rm (\Rightarrow)\ \ $ The solution is unique $\rm\ (mod\,\ mn)\ $ since if $\rm\ x',\:x\ $ are solutions then $\rm\ x'\equiv x\ $ mod $\rm\:m,n\:$ therefore $\rm\ m,n\ |\ x'-x\ \Rightarrow\ mn\ |\ x'-x\ \ $ since $\rm\ \:m,n\:$ coprime $\rm\:\Rightarrow\ lcm(m,n) = mn\ \ \ $ QED

Note $\ $ Easy CRT is not only easy to apply, but also very easy to remember. Namely note that $\rm\ x\equiv a\pmod{\! m}\iff x = a + m\,k,\:$ for some integer $\rm\:k,\,$ This further satisfies the second congruence $ $ iff $\ \rm mod\ n\!:\ x = a + m\,k\equiv b$ $\iff$ $\rm k\:\equiv (b-a)/m,\, $ thus the Easy CRT formula. This explains the $(\Leftarrow)$ proof: $ $ fill in the dots in: $\rm\:x\equiv \color{#0a0}a + \color{#c00}m\ [\,\cdots\,]\:$ to make it $\rm\equiv \color{#90f}b\pmod{\! n},\,$ viz. the $\rm\,m\,$ in the denominator cancels $\rm\,\color{#c00}m,\,$ and then the $\rm\,\color{90f}b\color{0a0}{-a}\,$ in the numerator cancels $\,\rm\color{#0a0}a\,$ then adds the sought $\,\rm\color{#90f}b\,$ to obtain $\,\rm x\equiv b\pmod{\!n},\,$ exactly what was done in the above algebra solving for $\,\rm x.$

See here and here for various methods to compute the modular inverses (or fractions) in the above CRT formula.

The above Theorem easily generalizes to noncoprime moduli as follows.

General Easy CRT $ $ The congruence system below is solvable $\!\iff\! \color{#c00}{\color{darkorange}d:=\gcd(m,n)\mid a-b}.\,$ When solvable the solution is $\,\color{#0a0}{{\rm unique}\ \bmod mn/\color{darkorange}d}\,$ as given below.

$$\begin{align} &x\equiv\!\ a\!\!\!\pmod{\! m}\\ &x\equiv\:\! b\!\!\!\pmod{\! n}\end{align}\iff\ x \equiv\, a + m\ \bigg[\frac{(b-a)/\color{darkorange}d}{m/\color{darkorange}d}\bmod{n/\color{darkorange}d}\,\bigg]\!\!\!\pmod{\!\color{#0a0}{mn/\color{darkorange}d}}$$

Proof $ $ The solvability $\rm\color{#c00}{criterion}$ is proved here. For $\rm\color{#0a0}{uniqueness}$, if $\,x,\bar x\,$ are both solutions then $\,x\equiv a\equiv \bar x\pmod{\!m}\,$ so $\,m\mid x-\bar x.\,$ Similarly $\,n\mid x-\bar x,\,$ so $\,{\rm lcm}(m,n) = \color{#0a0}{mn/\color{darkorange}d}\mid x-\bar x,\,$ as in CCRT. The solution formula can be obtained by specializing that in the first theorem using modular fractions by cancelling $\,\color{darkorange}{d\,\ \rm everywhere}$ in the bracketed fraction, or derived directly, viz. $\,x\equiv a\pmod{\!m}\!\iff\! x = a + km\,$ for some $\,k\in\Bbb Z,\,$ which will satisfy the 2nd congruence $$\begin{align} \iff \bmod n\!:\quad b\,\equiv\, x\,&\equiv\,\ a+km\\[.2em] \iff\! km\,&\equiv\ \, b-a,\,\ \text{so cancelling }\, \color{darkorange}{d\,\ \rm everywhere}\\[.2em] \iff \bmod n/\color{darkorange}d\!:\,\ km/\color{darkorange}d\, &\equiv\, (b-a)/\color{darkorange}d,\,\ \ {\rm by}\,\ \color{#c00}{d\mid a-b}\\[.2em] \iff k &\equiv \frac{(b-a)/\color{darkorange}d}{m/\color{darkorange}d},\ \ {\rm by}\,\ (m/d,n/d)=1\end{align}$$

The solvability criterion extends to any number of congruences, i.e. the system is solvable iff each pair is solvable as above, and we can use the above method to replace any pair of congruences by an equivalent single congruence, so iterating we eventually reach a single congruence which is equivalent to the system. This is often the easiest general way to solve such congruence systems. For a worked example see this answer.

Worth emphasis: the Easy CRT formula is viewable as a special case of the mod Distributive Law. This viewpoint yields an operational form of CRT that proves very convenient for calculation.

Beware $\ $ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. Then $\,a/b := ab^{-1}\,$ uniquely exists and fraction arithmetic works as usual for such modular fractions. See here for further discussion.