|
|
|
|
|
|
|
|
Solution
|
Solution provided by AtoZmath.com
|
|
|
|
Extended Euclidean Algorithm 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. Extended Euclidean Algorithm for `11` and `12`Solution:`y-=z^(-1)\ ("mod "n)-=11^(-1)\ ("mod "12)-=11\ ("mod "12)` Extended Euclidean Algorithm | 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 | | 11 | 0 | 1 | | 3 | `12-:11=1` | `12-1xx11=1` | `1-1xx0=1` | `0-1xx1=-1` | | 4 | `11-:1=11` | `11-11xx1=0` | `0-11xx1=-11` | `1-11xx-1=12` |
we get answer by taking the last non-zero row for Remainder `r=1` (gcd), `s=1,t=-1` Showing the identity, we have `12s+11t = gcd(12,11)=1` `12(1)+11(-1)=1`
|
|
|
|
|
|
