1. Chinese Remainder Theorem to solve `x=2 (mod 5),x=3 (mod 7),x=10 (mod 11)`

Solution:
`x-=2\ ("mod "5)->(1)`

`x-=3\ ("mod "7)->(2)`

`x-=10\ ("mod "11)->(3)`

`a_1=2,a_2=3,a_3=10`

`n_1=5,n_2=7,n_3=11`

Check if each `n_i` is pairwise coprime

`GCD(5,7)=1`

`GCD(5,11)=1`


`GCD(7,11)=1`


since all gcd is 1, so each `n_i` is pairwise coprime

There is a unique solution modulo N
`N=n_1*n_2*n_3=5*7*11=385`

Step-1: `z_i = N / n_i`

`z_1 = N / n_1=385/5=77`

`z_2 = N / n_2=385/7=55`

`z_3 = N / n_3=385/11=35`

Step-2: find `y_i-=z_i^(-1)\ ("mod " n_i)` using Extended Euclidean Algorithm

`y_1-=z_1^(-1)\ ("mod "n_1)-=77^(-1)\ ("mod "5)-=2^(-1)\ ("mod "5)-=-2\ ("mod "5)`

`t=-2`

i	Quotient `q=r_1-:r_2`	Remainder `r=r_1-q*r_2`	`s=s_1-q*s_2`	`t=t_1-q*t_2`
1		5	1	0
2		77	0	1
3	`5-:77=0`	`5-0xx77=5`	`1-0xx0=1`	`0-0xx1=0`
4	`77-:5=15`	`77-15xx5=2`	`0-15xx1=-15`	`1-15xx0=1`
5	`5-:2=2`	`5-2xx2=1`	`1-2xx-15=31`	`0-2xx1=-2`
6	`2-:1=2`	`2-2xx1=0`	`-15-2xx31=-77`	`1-2xx-2=5`

we get answer by taking the last non-zero row for Remainder r, `t=-2`

`y_2-=z_2^(-1)\ ("mod "n_2)-=55^(-1)\ ("mod "7)-=6^(-1)\ ("mod "7)-=-1\ ("mod "7)`

`t=-1`

i	Quotient `q=r_1-:r_2`	Remainder `r=r_1-q*r_2`	`s=s_1-q*s_2`	`t=t_1-q*t_2`
1		7	1	0
2		55	0	1
3	`7-:55=0`	`7-0xx55=7`	`1-0xx0=1`	`0-0xx1=0`
4	`55-:7=7`	`55-7xx7=6`	`0-7xx1=-7`	`1-7xx0=1`
5	`7-:6=1`	`7-1xx6=1`	`1-1xx-7=8`	`0-1xx1=-1`
6	`6-:1=6`	`6-6xx1=0`	`-7-6xx8=-55`	`1-6xx-1=7`

we get answer by taking the last non-zero row for Remainder r, `t=-1`

`y_3-=z_3^(-1)\ ("mod "n_3)-=35^(-1)\ ("mod "11)-=2^(-1)\ ("mod "11)-=-5\ ("mod "11)`

`t=-5`

i	Quotient `q=r_1-:r_2`	Remainder `r=r_1-q*r_2`	`s=s_1-q*s_2`	`t=t_1-q*t_2`
1		11	1	0
2		35	0	1
3	`11-:35=0`	`11-0xx35=11`	`1-0xx0=1`	`0-0xx1=0`
4	`35-:11=3`	`35-3xx11=2`	`0-3xx1=-3`	`1-3xx0=1`
5	`11-:2=5`	`11-5xx2=1`	`1-5xx-3=16`	`0-5xx1=-5`
6	`2-:1=2`	`2-2xx1=0`	`-3-2xx16=-35`	`1-2xx-5=11`

we get answer by taking the last non-zero row for Remainder r, `t=-5`

Step-3: The solution, which is unique modulo 385, is
`x-=a_1*y_1*z_1+a_2*y_2*z_2+a_3*y_3*z_3\ ("mod "385)`

`:.x-=2*-2*77+3*-1*55+10*-5*35\ ("mod "385)`

`:.x-=-308-165-1750\ ("mod "385)`

`:.x-=-2223\ ("mod "385)`

`:.x-=87\ ("mod "385)`

---

Method-2: Successive substitution method
`x-=2\ ("mod "5)->(1)`

`x-=3\ ("mod "7)->(2)`

`x-=10\ ("mod "11)->(3)`

from (1)
`x-=2\ ("mod "5)`

Hence `x=2+5a`

Now from (2), `x-=3\ ("mod "7)`

`:. (2+5a)-=3\ ("mod "7)`

`:. 5a-=1\ ("mod "7)`

Here `5^(-1)-=3\ ("mod "7)`

`:. 3xx5a-=3xx1\ ("mod "7)`

`:. 15a-=3\ ("mod "7)`

`:. a-=3\ ("mod "7)`

Hence `a=3+7b`

But `x=2+5a`

`:.x=2+5(3+7b)`

`:.x=2+15+35b`

`:.x=17+35b`

Now from (3), `x-=10\ ("mod "11)`

`:. (17+35b)-=10\ ("mod "11)`

`:. 6+2b-=10\ ("mod "11)`

`:. 2b-=4\ ("mod "11)`

Here `2^(-1)-=6\ ("mod "11)`

`:. 6xx2b-=6xx4\ ("mod "11)`

`:. 12b-=24\ ("mod "11)`

`:. b-=2\ ("mod "11)`

Hence `b=2+11c`

But `x=17+35b`

`:.x=17+35(2+11c)`

`:.x=17+70+385c`

`:.x=87+385c`

`:.x-=87\ ("mod "385)`

---

---