1. Examples
1. Modular multiplicative inverse 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`
Here `t` is -ve, so add 12.
`:.t=-1+12=11`
`:.` multiplicative inverse `11` mod `12=11`
2. Modular multiplicative inverse for `7` and `11`
Solution:
`y-=z^(-1)\ ("mod "n)-=7^(-1)\ ("mod "11)-=8\ ("mod "11)`
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 | | 11 | 1 | 0 | | 2 | | 7 | 0 | 1 | | 3 | `11-:7=1` | `11-1xx7=4` | `1-1xx0=1` | `0-1xx1=-1` | | 4 | `7-:4=1` | `7-1xx4=3` | `0-1xx1=-1` | `1-1xx-1=2` | | 5 | `4-:3=1` | `4-1xx3=1` | `1-1xx-1=2` | `-1-1xx2=-3` | | 6 | `3-:1=3` | `3-3xx1=0` | `-1-3xx2=-7` | `2-3xx-3=11` |
we get answer by taking the last non-zero row for Remainder `r=1` (gcd), `s=2,t=-3`
Here `t` is -ve, so add 11.
`:.t=-3+11=8`
`:.` multiplicative inverse `7` mod `11=8`
3. Modular multiplicative inverse for `3` and `7`
Solution:
`y-=z^(-1)\ ("mod "n)-=3^(-1)\ ("mod "7)-=5\ ("mod "7)`
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 | | 7 | 1 | 0 | | 2 | | 3 | 0 | 1 | | 3 | `7-:3=2` | `7-2xx3=1` | `1-2xx0=1` | `0-2xx1=-2` | | 4 | `3-:1=3` | `3-3xx1=0` | `0-3xx1=-3` | `1-3xx-2=7` |
we get answer by taking the last non-zero row for Remainder `r=1` (gcd), `s=1,t=-2`
Here `t` is -ve, so add 7.
`:.t=-2+7=5`
`:.` multiplicative inverse `3` mod `7=5`
4. Modular multiplicative inverse for `60` and `36`
Solution:
`y-=z^(-1)\ ("mod "n)-=60^(-1)\ ("mod "36)-=24^(-1)\ ("mod "36)-=0\ ("mod "36)`
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 | | 36 | 1 | 0 | | 2 | | 60 | 0 | 1 | | 3 | `36-:60=0` | `36-0xx60=36` | `1-0xx0=1` | `0-0xx1=0` | | 4 | `60-:36=1` | `60-1xx36=24` | `0-1xx1=-1` | `1-1xx0=1` | | 5 | `36-:24=1` | `36-1xx24=12` | `1-1xx-1=2` | `0-1xx1=-1` | | 6 | `24-:12=2` | `24-2xx12=0` | `-1-2xx2=-5` | `1-2xx-1=3` |
we get answer by taking the last non-zero row for Remainder `r=12` (gcd), `s=2,t=-1`
Here gcd (Remainder r=12) is not 1, So 60 does not have a multiplicative inverse modulo 36
5. Modular multiplicative inverse for `35` and `20`
Solution:
`y-=z^(-1)\ ("mod "n)-=35^(-1)\ ("mod "20)-=15^(-1)\ ("mod "20)-=0\ ("mod "20)`
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 | | 20 | 1 | 0 | | 2 | | 35 | 0 | 1 | | 3 | `20-:35=0` | `20-0xx35=20` | `1-0xx0=1` | `0-0xx1=0` | | 4 | `35-:20=1` | `35-1xx20=15` | `0-1xx1=-1` | `1-1xx0=1` | | 5 | `20-:15=1` | `20-1xx15=5` | `1-1xx-1=2` | `0-1xx1=-1` | | 6 | `15-:5=3` | `15-3xx5=0` | `-1-3xx2=-7` | `1-3xx-1=4` |
we get answer by taking the last non-zero row for Remainder `r=5` (gcd), `s=2,t=-1`
Here gcd (Remainder r=5) is not 1, So 35 does not have a multiplicative inverse modulo 20
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
