# How to solve a congruence system?

Here is a tricky congruence system to solve, I have tried to use the Chinese Remainder Theorem without success so far.

$$2x \equiv3\;(mod\;7)\\ x\equiv8\;(mod\;15)$$

Thank you very much Li

You need to "get rid of" the $$2$$ from the right hand side of the first congruence in your system:

\begin{aligned} 2x & \equiv 3 \mod 7 & (1) \\ x & \equiv 8 \mod 15 & (2) \end{aligned}

So here, you have to multiply both sides of equation $$(1)$$ by the inverse of $$2$$ modulo $$7$$, which is $$4$$. This means the first equation becomes $$x \equiv 12 \equiv 5 \mod 7$$ So this leaves us with the system:

\color{blue}{\begin{aligned} x & \equiv 5 \mod 7 \\ x & \equiv 8 \mod 15 \end{aligned}}

Since $$\gcd(7, 15) = 1$$, there is a unique solution for $$x$$ modulo $$(7)(15) = 105$$. So we can use the Chinese remainder theorem on the system that is in $$\color{blue}{\mathrm{blue} }$$.

Now try using the Chinese remainder theorem. Recall for a system of two congruences:

$$x \equiv a_1 \mod n_1$$

$$x \equiv a_2 \mod n_2,$$ if $$\gcd(n_1, n_2) = 1$$, then the solution is given by:

$$x \equiv a_1 n_2 [n_2^{-1}]_{n_1} + a_2 n_1[n_1^{-1}]_{n_2},$$ where $$[p^{-1}]_{q}$$ means "the inverse of $$p$$ modulo $$q$$".

You will find this is the solution: $$x \equiv 5\cdot15\cdot1 + 8\cdot7\cdot13 \equiv \color{green}{803} \mod 105$$ and $$\color{green}{803} \equiv \color{red}{68} \mod 105,$$ so $$\boxed{\color{red}{x=68}}.$$

$$\color{red}{\mathrm{That}}$$ is the least positive residue solution, modulo $$105$$. Since anything congruent to $$68$$ modulo $$105$$ will also be a solution, you could also say $$\boxed{x=105n+68}$$ for each integer $$n$$.

$$2x = 3(mod 7)$$ $$x+x= 3(mod 7)$$ $$x = 5(mod 7)$$ $$x = 8(mod 15)$$ $$x = 15k_1 + 8$$ $$x = 7k_2 + 5$$ $$x = 105k_3 + c$$ $$0 \le c < 7*15$$ $$c(mod 7)=5$$ $$c = 15k_4+8$$ $$0 \le k_4 < 7$$ $$(15k_4+8)(mod 7)=3$$ $$k_4 + 1 = 5$$ $$k_4 = 4$$ $$c=15*4+4 => c=68$$ $$x = 105k_3 + 68$$ $$0 \le k_3 <\infty$$ $$k_3 \in Z$$

$$\begin{split} X&=15L+8\\ 2X&=30L+16=30(7m+u)+16 \end{split}$$ [ where $$u$$ can be $$0,1,2,3,4,5,6$$] $$2X=(210m+28u+14)+(2u+2)$$ So $$2u+2$$ must leave remainder $$3$$ when divided by $$7$$,thus $$\begin{split} u&=4\\ 2X&=210m+136. \end{split}$$ Therefore $$X=105m+68$$.