Getting an X for Chinese Remainder Theorem (CRT)

Question

how do I get modulo equations to satisfy a given X in CRT.

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?

Answer 1

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

Answer 2

Here is a much, 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 look for hidden innate symmetries in a problem before diving head-first into brute-force mechanical calculations! Here the key insight is that the equations split into pairs with obvious constant solutions, viz.

$\rm\quad\quad\quad\quad\quad x\equiv \ \ \ 2\ \ \:(mod\ 7),\ \ x\equiv \ \ \ 2\ \ \:(mod\ 11)\ \iff\ x\equiv \ \ \ 2\ \ (mod\ 77)$

$\rm\quad\quad\quad\quad\quad x\equiv -1\ \ (mod\ 5),\ \ x\equiv -1\ \ (mod\ 13)\ \iff\ x\equiv -1\ \ (mod\ 65)$

So we reduced the four original LHS equations to the two RHS equations. $\: $ Now we apply a simple version of the Chinese Remainder Theorem to solve the RHS equations. $\ $ By Easy CRT below

$\rm\quad\quad\quad\quad\quad x\equiv\ 2 + 77\ \bigg[\displaystyle\frac{-3}{77}\ mod\ 65\bigg]\ \ (mod\ 77\cdot65)$

Now $\rm\displaystyle\ \ \ \ \ mod\ \ 65:\ \ \ \ \ \frac{-3}{77}\ \equiv\ \frac{-3}{12}\ \equiv\ \frac{-1}4\ \equiv\ \frac{64}4\ \equiv\ 16$

Hence $\rm\ \ x\ \equiv\ 2 + 77\cdot 16\ \equiv\ 1234\ \ (mod\ 77\cdot 65)\quad\quad\ $ QED

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

$\rm\displaystyle\quad\quad\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\ m\:n)\ $ since if $\rm\ x',\:x\ $ are solutions then $\rm\ x'\equiv x\ $ mod $\rm\:m,n\:$ therefore $\rm\ m,\:n\ |\ x'-x\ \Rightarrow\ m\:n\ |\ x'-x\ \ $ since $\rm\ \:m,\:n\:$ coprime $\rm\:\Rightarrow\ lcm(m,n) = m\:n\:.\quad $ QED

Note $\ $ Easy CRT is not only easy to apply, but also very easy to remember. Namely note $\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,\ $ hence the "Easy CRT" solution. This enables the $(\Leftarrow)$ proof, i.e. fill in the dots in $\rm\:a + m\ [\,\cdots\,]\:$ so that it is $\rm\equiv b\pmod n\:$

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