|
|
|
|
|
|
|
|
Solution
|
Solution provided by AtoZmath.com
|
|
|
|
Chinese Remainder Theorem calculator
|
1. Chinese Remainder Theorem
 1. x=2 (mod 5),x=3 (mod 7),x=10 (mod 11)
2. x=4 (mod 10),x=6 (mod 13),x=4 (mod 7),x=2 (mod 11)
3. x=6 (mod 11),x=13 (mod 16),x=9 (mod 21),x=19 (mod 25)
4. 3x=7 (mod 10)
5. 3x=6 (mod 12)
6. 2x=5 (mod 7),3x=4 (mod 8)
7. 2x=1 (mod 3),3x=5 (mod 8)
8. 2x=6 (mod 14),3x=9 (mod 15),5x=20 (mod 60)
9. x=3 (mod 7),x=3 (mod 5),x=4 (mod 12)
10. x=1 (mod 4),x=0 (mod 6)
2. Modulo
1. 42 mod 5
2. 3^302 mod 5
3. 19^24 mod 21
4. 7^106 mod 143
5. 27^400 mod 619
6. 42^-1 mod 5
3. Extended Euclidean Algorithm, Euclid's Algorithm, Modular multiplicative inverse
1. 11 and 12
2. 7 and 11
3. 3 and 7
|
Example1. 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` `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)` |
|
|
|
|
|
