Solve three congruences using CRT

Question

How do I solve the following Congruences=

$c ≡ 1 \mod 143$

$c ≡ 315 \mod 323$

$c ≡ 167 \mod 667$

I know that the moduli are coprime so there will be a unique solution. Secondly, I know that the solutions will be in $\mod 143 * 323 *667$... Please help.

Answer 1

Hint: Solve for the first two congruences to begin with. You'll get a solution $\gamma\bmod 143\cdot 323$. Then solve for the system $$\begin{cases} c\equiv \gamma &\bmod 143\cdot 323,\\ c\equiv 167&\bmod 667. \end{cases}$$ For a system of 2 congruences with coprime moduli: $$\begin{cases} c\equiv \alpha &\bmod a,\\ c\equiv \beta&\bmod b, \end{cases}$$ one starts from a Bézout's relation between $a$ and $b$: $\;ua+vb=1$. The solutions are given by: $$c\equiv \beta ua+\alpha vb\mod ab.$$ The Bézout's relation can be found with the extended Euclidean algorithm.

Answer 2

$143=11\cdot 13$ and $323=17\cdot 19$ and $667=23\cdot 29$, so $143,323,667$ are pairwise coprime,

so by the Chinese Remainder Theorem a solution $x$ exists, and is in the form $x\equiv r\pmod{143\cdot 323\cdot 667}$ for some $r\in\mathbb Z$.

$c\equiv 1\pmod{143}\iff c=143k+1$ for some $k\in\mathbb Z$.

$c\equiv 315\pmod{323}\iff 143k\equiv 314\pmod{323}$.

$\iff k\equiv 314\cdot 143^{-1}\pmod{323}$.

Now, to find $143^{-1}\bmod {323}$, you can apply the Extended Euclidean Algorithm.

Subtract consecutive rows:

$$323=(1)(323)+(0)(143)\\ 143=(0)(323)+(1)(143)\\37=(1)(323)+(-2)(143)\\ 32=(-3)(323)+(7)(143)\\5=(4)(323)+(-9)(143)\\2=(-27)(323)+(61)(143)\\1=(58)(323)+(-131)(143)$$

Therefore $(-131)(143)\equiv 1\pmod{323}$, so $143^{-1}\equiv -131\equiv 192\pmod{323}$.

$k\equiv 314\cdot 192\equiv 210\pmod{323}$.

$\iff k=323t+210$ for some $t\in\mathbb Z$.

$c=143(323t+210)+1=46189t+30031$.

$c\equiv 167\pmod{667}\iff 166t\equiv 151\pmod{667}$

$\iff t\equiv 151\cdot 166^{-1}\pmod{667}$

Again, use the Extended Euclidean Algorithm to find $166^{-1}\bmod 667$:

Subtract consecutive rows:

$$667=(1)(667)+(0)(166)\\166=(0)(667)+(1)(166)\\3=(1)(667)+(-4)(166)\\1=(-55)(667)+(221)(166)$$

Therefore $(221)(166)\equiv 1\pmod{667}$, so $166^{-1}\equiv 221\pmod{667}$.

$t\equiv 151\cdot 221\equiv 21\pmod{667}$.

$\iff t=667h+21$ for some $h\in\mathbb Z$.

$c=46189(667h+21)+30031=(143\cdot 323\cdot 667)h+1000000$.

This agrees with WolframAlpha.

Answer 3

Let $M = 143\cdot 323 \cdot 667$, now let $M_1 = \frac{M}{143}, M_2 = \frac{M}{323}, M_3 = \frac{M}{667}$.
Now let,

$y_1 = M_1^{-1}$ in $\mathbb{Z}_{143}$
$y_2 = M_2^{-1}$ in $\mathbb{Z}_{323}$
$y_3 = M_3^{-1}$ in $\mathbb{Z}_{667}$

And now we have $x = 1 \cdot M_1 \cdot y_1 + 315 \cdot M_2 \cdot y_2 + 167 \cdot M_3 \cdot y_3$ is one solution to all of the congruences (and as you said all solutions are congruent modulo $M$).