How to solve this problem in the image below

Question

I am trying to do my best but I am new on this website so there may be some problems with my formatting, So it's a humble request if you think that you can correct my formate plz do it

[

I tried to solve this system by Chinese Remainder Theorem

As here $a_1 =1$, $a_2=4$ and $a_3=6$ and $m_1=3$, $m_2=5$, and $m_3=7$ so by applying the Chinese remainder theorem here $m= 3\times 5\times 7$

so $m_1= m/3 = 35$, similarly $m_2=21$ and $m_3=15$ now the linear congruences are $$35x_1\equiv 1 \pmod 3,\quad 21x_2\equiv 1 \pmod 5,\quad 15x_3\equiv 1\pmod7 $$

So in the book the values of $x_1\equiv 2,\ x_2\equiv 1$ and $x_3\equiv 1$ so my doubt is this how the values of $x_1, x_2$ and $x_3$ are determined.

Answer 1

So $x = 1 + 3k= 4 + 5j$. So $3k - 5j \equiv 3 \mod 15$. $k=1,j=0$ and $x \equiv 4 \mod 15$ is such a solution.

So $x = 4 + 15m = 6 + 7n$. So $15m-7n = 2$. By Bezout's lemma we know $15a + 7b = 1$ exist and with less thought than effort $15*1 + 7*(-2) = 1$ so $15(2) -7(4) = 2$ and $x \equiv 4 + 15*2 = 6 + 7*4 = 34 \equiv 7*15$ is also a solution.

So by CRT $x \equiv 34 \mod 105$ is the unique class of solutions.

Answer 2

Well, let us see what the CRT proof says:

(1) $\;N:=3\cdot5\cdot7=105\;$

(2) $$t_1:=\frac N3=35\;,\;\;t_2:=\frac N5=21\;,\;\;t_3:=\frac N7=15$$

(3)$$\begin{cases} w_1:=t_1^{-1}\pmod 3=2^{-1}\pmod 3=2\\{}\\ w_2:=t_2^{-1}\pmod5=1^{-1}\pmod 5=1\\{}\\ w_3:=t_3^{-1}\pmod 7=1^{-1}\pmod7=1\end{cases}$$

and thus a solution to your system is given by the integer

$$x:=\sum_{k=1}^3a_kt_kw_k\;,\;\;a_1:=1\,,\,\,a_2:=4\,,\,\,a_3:=6\implies$$

$$x=1\cdot35\cdot2+4\cdot21\cdot1+6\cdot15\cdot1=244$$

and if you want the unique solution modulo $\;N\;$ , then you just have to take

$$\;\overline x=244\pmod{105}=34\pmod{105}\;$$

Check all the above and, in particular, check here a simplified yet very useful proof of the CRT for the integers $\;\Bbb Z\;$ . If you know this you'll be able to do any such problem, and not matter how many equations (equivalences) you are given.

Answer 3

Note that

• $x\equiv 1 \pmod 3\implies x=1+3k $
• $x\equiv 4 \pmod 5\implies 1+3k\equiv4 \pmod 5\\\implies k\equiv 1\pmod 5\implies x= 1+3(1+5h)=4+15h$
• $x\equiv 6 \pmod 7\implies 4+15h\equiv 6 \pmod7 \implies 15h \equiv 2 \pmod 7\\\implies h\equiv 2 \pmod 7 \\\implies x=4+15(2+7r)=34+105r $

thus

$$x\equiv 34 \pmod {105}$$

Answer 4

$x_1,\ x_2$ and $x_3$ are obtained as follows

• $x_1$ is the inverse of $35\bmod 3$. Now $35\equiv 2$, so its inverse is $2$ since $2\cdot 2\equiv 1\mod 3$.
• Similarly, $x_2$ is the inverse of $21\bmod 5$. However $21\equiv 1\mod 5$, so it is its own inverse.
• Last, $x_3$ is the inverse of $15\bmod 7$, and again $15\equiv 1\mod 7$.

Note 1 :

The modular inverses are easy to calculate here by trial and error. In the general case, with bigger numbers, or for programming, you have to use the extended Euclidean algorithm, which yields a Bézout's relation between two coprime numbers: $$x_1m_1+x_2m_2=1.$$ Considering this relation mod $m_2$, you get $\;x_1m_1\equiv 1\mod m_2$, so $x_1$ is the inverse of $m_1\bmod m_2$. Similarly for the inverse of $m_2\bmod m_1$.

Note 2:

The formula to solve the system of (three) linear congruences $$\begin{cases}x\equiv \alpha_1\mod m_1\\x\equiv \alpha_2\mod m_2\\x\equiv \alpha_3\mod m_3\end {cases}\qquad(\text{moduli pairwise coprime}),$$ uses a Bézout's relation between $M_1=m_2m_3$, $\;M_2=m_3m_1$, $\;M_3=m_1m_2$: $$ x_1M_1+x_2M_2+x_3M_3=1, $$ and the solution is $$x\equiv \alpha_1x_1M_1+\alpha_2x_2M_2+\alpha_3x_3M_3 \mod m_1m_2m_3. $$ This formula is the exact modular analogue of Lagrange's interpolation polynomial (for quadratic polynomials in the present case).