Chinese Remainder Theorem to solve `x=3 (mod 7),x=3 (mod 5),x=4 (mod 12)`

Solution:
`x-=3\ ("mod "7)->(1)`

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

`x-=4\ ("mod "12)->(3)`

`a_1=3,a_2=3,a_3=4`

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

Check if each `n_i` is pairwise coprime

`GCD(7,5)=1`

`GCD(7,12)=1`


`GCD(5,12)=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=7*5*12=420`

Step-1: `z_i = N / n_i`

`z_1 = N / n_1=420/7=60`

`z_2 = N / n_2=420/5=84`

`z_3 = N / n_3=420/12=35`

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

`y_1-=z_1^(-1)\ ("mod "n_1)-=60^(-1)\ ("mod "7)-=4^(-1)\ ("mod "7)-=2\ ("mod "7)`

`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		7	1	0
2		60	0	1
3	`7-:60=0`	`7-0xx60=7`	`1-0xx0=1`	`0-0xx1=0`
4	`60-:7=8`	`60-8xx7=4`	`0-8xx1=-8`	`1-8xx0=1`
5	`7-:4=1`	`7-1xx4=3`	`1-1xx-8=9`	`0-1xx1=-1`
6	`4-:3=1`	`4-1xx3=1`	`-8-1xx9=-17`	`1-1xx-1=2`
7	`3-:1=3`	`3-3xx1=0`	`9-3xx-17=60`	`-1-3xx2=-7`

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

`y_2-=z_2^(-1)\ ("mod "n_2)-=84^(-1)\ ("mod "5)-=4^(-1)\ ("mod "5)-=-1\ ("mod "5)`

`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		5	1	0
2		84	0	1
3	`5-:84=0`	`5-0xx84=5`	`1-0xx0=1`	`0-0xx1=0`
4	`84-:5=16`	`84-16xx5=4`	`0-16xx1=-16`	`1-16xx0=1`
5	`5-:4=1`	`5-1xx4=1`	`1-1xx-16=17`	`0-1xx1=-1`
6	`4-:1=4`	`4-4xx1=0`	`-16-4xx17=-84`	`1-4xx-1=5`

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 "12)-=11^(-1)\ ("mod "12)-=-1\ ("mod "12)`

`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		12	1	0
2		35	0	1
3	`12-:35=0`	`12-0xx35=12`	`1-0xx0=1`	`0-0xx1=0`
4	`35-:12=2`	`35-2xx12=11`	`0-2xx1=-2`	`1-2xx0=1`
5	`12-:11=1`	`12-1xx11=1`	`1-1xx-2=3`	`0-1xx1=-1`
6	`11-:1=11`	`11-11xx1=0`	`-2-11xx3=-35`	`1-11xx-1=12`

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

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

`:.x-=3*2*60+3*-1*84+4*-1*35\ ("mod "420)`

`:.x-=360-252-140\ ("mod "420)`

`:.x-=-32\ ("mod "420)`

`:.x-=388\ ("mod "420)`

---

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

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

`x-=4\ ("mod "12)->(3)`

from (1)
`x-=3\ ("mod "7)`

Hence `x=3+7a`

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

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

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

`:. 2a-=0\ ("mod "5)`

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

`:. 3xx2a-=3xx0\ ("mod "5)`

`:. 6a-=0\ ("mod "5)`

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

Hence `a=0+5b`

But `x=3+7a`

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

`:.x=3+0+35b`

`:.x=3+35b`

Now from (3), `x-=4\ ("mod "12)`

`:. (3+35b)-=4\ ("mod "12)`

`:. 3+11b-=4\ ("mod "12)`

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

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

`:. 11xx11b-=11xx1\ ("mod "12)`

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

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

Hence `b=11+12c`

But `x=3+35b`

`:.x=3+35(11+12c)`

`:.x=3+385+420c`

`:.x=388+420c`

`:.x-=388\ ("mod "420)`

---

---