Solving $\ge 2$ congruences by CRT = Chinese Remainder Theorem

Question

How do I get the solution given by CRT to match another solution, e.g. the least positive?

For example say I have X = 1234. I choose mi as 5, 7, 11, 13. This satisfies the simple requirements of Mignotte's threshold secret sharing scheme. More precisely given in my example k = n = 4, and the product of any k - 1 is smaller then X how come simply computing the remainder of each won't give equations that solve to X = 1234.

In the case of the example,

x = 4 mod 5
x = 2 mod 7
x = 2 mod 11
x = 12 mod 13

Which resolves to 31264 (won't CRT produce the smallest?)

Any hints?

---

Below is the solution linked to on "Math Celebrity" (cached to avoid link rot).

Answer 1

As proved in General Easy CRT below, solutions of such congruence systems are necessarily unique $\!\bmod M = $ lcm of all moduli. But a CRT algorithm (or formula) need not always return the least nonnegative solution, so we must reduce it $\!\bmod M\,$ if we seek such a normalized solution. Doing so in the OP we get $\,31264\bmod 5005 \equiv 1234,\,$ where $\,M = 5005 = {\rm lcm}(5,7,11,13)$.

Below is a much simpler way to immediately obtain the 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. Tip: search for hidden innate structure in a problem before diving head-first into brute-force mechanical calculations.

Below we use modular fractions $\,a/b := ab^{-1}\pmod{\! n}.\,$ They are well defined when $\,b\,$ is invertible $\!\bmod n,\,$ i.e. when $\,b\,$ is coprime to $\,n.\,$ Generally common fraction arithmetic is valid $\!\bmod n\,$ provided we restrict to such fractions with denominator coprime to $\,n\,$ (see here).

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\qquad$$

Thus the above $4$ original LHS equations are equivalent to the above $2$ RHS equations. The latter $2$ 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),\ $ so computing the fraction

by twiddling $\: \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)

thus we get $\rm\ \ x\, \equiv\, \color{#0a0}{2 + 77}\,[\,\color{#d0f}{16}\,] \equiv 1234\ \ (mod\ 77\cdot 65)$. $\ \ \bf\small QED$

---

Or $\: x\!-\!\color{#0a0}2\bmod \color{#0a0}{77}(65) = \color{#0a0}{77}\left[\dfrac{\color{#c00}x\!-\!2}{77}\bmod 65\right] = 77\left[\dfrac{\color{#c00}{-1}\!-\!2}{77}\bmod \color{#c00}{65}\right]\! = 77(\color{#d0f}{16}) $ as above, by employing $\:\color{#0a0}ab\bmod \color{#0a0}ac = \:\color{#0a0}a\:[\,b\bmod c]\,$ (mod Distributive Law) to factor $\,\color{#0a0}{a \!=\! 77}\,$ out of a $\!\bmod\!.$

As above, the Easy CRT formula is viewable as a special case of the mod Distributive Law, which yields an operational form of CRT that proves very convenient for calculation.

---

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

$$\begin{eqnarray} x&\equiv&\!\ a\!\!\pmod{\!m} \\ x&\equiv&\!\ b\!\!\pmod{\!n}\end{eqnarray}\! \iff x \equiv\, a + m\ \bigg[\frac{b-a}{m}\bmod n\,\bigg]\!\!\!\pmod{\!mn}\qquad$$

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

$ (\Rightarrow)\ \ $ Solutions are unique $\bmod mn\ $ since if $\ x',\,x\ $ are solutions then $\ x'\equiv x\ $ mod $\,m\ \&\ n\,$ therefore $\ m,n\ |\ x'-x\ \Rightarrow\ mn\ |\ x'-x\ \ $ since $\ \,m,n\,$ coprime $\,\Rightarrow\ {\rm lcm}(m,n) = mn$. $\ \ \bf\small QED$

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

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

---

The Theorem generalizes to noncoprime moduli by cancelling $\,\color{darkorange}{d=\gcd(m,n)\,\ \rm everywhere}$.

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} = {\rm lcm}(m,n)\,$ 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}}\qquad$$

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+k\,m\\[.2em] \iff\quad\ \ k\,m\,&\equiv\ \, b-a,\,\ \text{so cancelling }\, \color{darkorange}{d\,\ \rm everywhere}\\[.2em] \iff \bmod n/\color{darkorange}d\!:\,\ k\,m/\color{darkorange}d\, &\equiv\, (b-a)/\color{darkorange}d,\,\ \ {\rm by}\,\ \color{#c00}{\color{darkorange}d\mid a-b}\\[.3em] \iff\qquad\ \ \ k &\equiv \frac{(b-a)/\color{darkorange}d}{m/\color{darkorange}d},\ \ {\rm by}\,\ (m/d,n/d)=1.\ \ \ \bf\small QED\end{align}\qquad$$

---

Efficiently solving $\,n > 2\,$ congruences a pair at a time using the above method

The solvability criterion extends to any number of congruences, i.e. the system is solvable iff each pair is solvable - as above. Thus when the system is solvable 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 (its uses only efficient gcd operations vs. inefficient prime factorization used in alternative methods). For a worked example see this answer.

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.

---

CRT solution via fractional extended Euclidean algorithm

$\begin{align} x&\equiv 1\!\!\!\pmod{\!8}\\ x&\equiv 7\!\!\!\pmod{\!125}\end{align}$ $\iff \begin{align} 125x&\equiv 125\!\!\!\pmod{\!1000}\\ 8x&\equiv 56\pmod{\!1000}\end{align}$

${\rm mod}\ 1000\!:\,\ x\equiv \dfrac{125}{125} \overset{\large\frown}\equiv \dfrac{56}{\color{#90f}{8}} \overset{\large\frown}\equiv \dfrac{\color{#c00}{229}}{\color{#0a0}{-3}} \overset{\large\frown}\equiv \dfrac{-257}{-1}$

$\!\begin{array}{rrl} \text{or, equationally:}\ \ \ [\![1]\!]\!\!\!& 125\,x\!\!\!&\equiv\ \ 125\\ [\![2]\!]\!\!\!&\ \color{#90f}{8}\,x\!\!\!&\equiv\ \ \ \ 56\\ [\![1]\!]-16[\![2]\!]\equiv:[\![3]\!]\!\!\!&\ \color{#0a0}{{-}3}\,x\!\!\!&\equiv\,\ \ \color{#c00}{229}\\ [\![2]\!]\ +\ 3[\![3]\!]\equiv:[\![4]\!]\!\!\!&\ {-}x\!\!\! &\equiv {-}257\\ \end{array}$

---

Below is a simple example with noncoprime moduli (from here)

$\begin{align} x&\equiv 6\!\!\!\pmod{\!10}\\ x&\equiv 8\!\!\!\pmod{\!12}\end{align}\!$ $\underset{\times 5}{\overset{\times 6}\iff} \begin{align} 6x&\equiv 36\!\!\!\pmod{\!60}\\ 5x&\equiv 40\!\!\!\pmod{\!60}\end{align}$

${\rm mod}\,\ 60\!:\,\ x\equiv \dfrac{36}{6} \overset{\large\frown}\equiv \dfrac{40}{\color{#90f}{5}} \overset{\large\frown}\equiv \dfrac{\color{#c00}{-4}}{\color{#0a0}{1}} $

$\!\begin{array}{rrl} \text{equationally:} \ \ [\![1]\!]\!\!\!&\ 6\,x\!\!\!&\equiv\ 36\\ [\![2]\!]\!\!\!&\ \color{#90f}{5}\,x\!\!\!&\equiv \ 40\\ [\![1]\!]-[\![2]\!]\equiv:[\![3]\!]\!\!\!&\ \color{#0a0}{1}\,x\!\!\!&\equiv \color{#c00}{-4} \end{array}$

Answer 2

The final result of the CRT calculation must be reduced modulo 5 x 7 x 11 x 13 = 5005. This gives the correct answer.