|
1. Chinese Remainder Theorem example
( Enter your problem )
|
|
|
2. Example-2 : x=3 (mod 7),x=3 (mod 5),x=4 (mod 12)
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)`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
|
|
