Solving System of Congruence using Chinese Remainder Theorem

Question

I'm trying to solve a system of congruence using CRT

$$x≡2\pmod3\\ x≡3\pmod5\\ x≡2\pmod7$$

My approach is

First calcuating $m_1,m_2,m_3$ then M followed by inverses of $m_1,m_2$ and $m_3$ and finally applying to the formulae for $x=(a_1\cdot m_1\cdot m_1 inv+.....)$

How is the multiplicative inverse of $m_1$ found eg: in this case $m_1=35$. How is $m_1$ inv calculated?

Answer 1

Firstly, $x^{-1} \pmod{y}$ is defined as: $x^{-1}*x \equiv x*x^{-1}\equiv1 \pmod{y}$

The solution of the problem can be made as:

$x=3a+2=5b+3=7c+2$

Take $3a+2=7c+2 \implies 3a=7c$

Take Least Common Multiple $\operatorname{lcd}[3,7]=21$

Then, $x=21k+2$ for some $k$.

Now, $21k+2=5b+3 \implies 21k=5b+1 \implies 21k\equiv1 \pmod{5}\implies k\equiv 1 \mod{5}$ $\implies k=5n+1$

Then the solution we're looking for is:

$x=21(5n+1)+2=23+105n, n\in \mathbb{N}$