Chinese Remainder Theorem, when the moduli are pairwise coprime. 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.
 A: 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. $$
A: Two suggestions:  
First is that since $y$ is the inverse of $x$ in each of the three congruences, you need only invert $x\pmod {108}$ to get the result.   This can be done via the Euclidean Algoirthm.
Second:  First solve the three congruences for $y$.  We get $$y\equiv 2 \pmod 3\quad \&\quad  y\equiv 2 \mod 5\quad \&\quad y\equiv 3 \pmod 7$$
now solve as before.  This method has the advantage that you don't need all three congruences to be $\equiv 1$.  
A: Easiest to  reuse the computed CRT formula from your calculation of $x$, i.e. we know
$$\ \ \ \ \ \ \ \ \  z \equiv (a,b,c)\!\pmod{3,5,7}\iff z\equiv -35\,a\,+\,21\,b\,+\,15\,c\!\pmod{\!105}$$
$\begin{align}{\rm so}\qquad x&\equiv (\color{#0a0}{2,3,5})\!\pmod{3,5,7}\iff x\equiv -35(\color{#0a0}2)\!+\!21(\color{#0a0}3)\!+\!15(\color{#0a0}5)\equiv 68\!\!\pmod{\!105}\\[.2em] 
\iff\, y\equiv \,x^{-1}\!&\equiv (\color{#c00}{2,2,3})\!\pmod{3,5,7}
\iff y\equiv -35(\color{#c00}2)\!+\!21(\color{#c00}2)\!+\!15(\color{#c00}3)\equiv 17\!\!\pmod{\!105}
\end{align}$
A: we can write $$x=2+k_13,x=3+k_25,x=5+7k_3$$.By the first two equations we get
$$3k_1-5k_2=1$$. Since the $$k_i$$ are integers we get $$k_1=2+5C,k_2=1+3C$$ where $C$ is an integer number.
So we get $$x=8+15C$$ using this for the third equation we get $$8+15C=5+7k_3$$. $C=4$ fullfils our equation so we get $x=68$.
