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. $$

Answer 2

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$.

Answer 3

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$.

Answer 4

Easiest to reuse the computed CRT formula from your calculation of $\,x,\,$ i.e. we know

$\!\!\begin{align} z &\equiv (a,b,c)\!\pmod{\!3,5,7}\iff z\equiv \,-35\,a\,+21\,b\,+\,15\,c\!\pmod{\!105}\\[.3em] {\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}\\[.3em] \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}$