Chinese Remainder Theorem, when the moduli are pairwise coprime.

Question

I'm trying to learn the Chinese Remainder Theorem and I've run into some problem. The problem I am to solve goes like:

Find all $x ∈ Z$ such that

$x≡2\pmod{3}$

$x≡3\pmod{5}$

$x≡5\pmod{7}$

Also, find all $y ∈ Z$ such that

$x*y≡1\pmod{3}$

$x*y≡1\pmod{5}$

$x*y≡1\pmod{7}$

I can solve the first part and get that $x=68+105m$, where $m ∈ Z$.
But when I try to tackle the second part I get stuck. I get:

$68y+105my≡1\pmod{3}, \pmod{5}, \pmod{7}$

I don't know how I can reduce the problem and make it easier. Some help please.

Answer 1

By the Chinese remainder theorem, this amounts to finding the inverse of $68\bmod 105$. The standard method is the extended Euclidean algorithm: \begin{array}{rrrl} r_i&u_i&v_i&q_i \\ \hline 105 & 0 & 1 \\ 68 & 1 & 0 & 1 \\ \hline 37 & -1 & 1 & 1 \\ 31 & 2 & -1 & 1 \\ 6 & -3 & 2 & 5 \\ 1 & \color{red}{17}& -11 & \\ \hline \end{array} So the solutions are $$y\equiv 17 \mod 105. $$