1. 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`
2. Extended Euclidean Algorithm 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`
Showing the identity, we have `11s+7t = gcd(11,7)=1`
`11(2)+7(-3)=1`
3. Extended Euclidean Algorithm 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`
Showing the identity, we have `7s+3t = gcd(7,3)=1`
`7(1)+3(-2)=1`
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
