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