Rozszerzony algorytm Euklidesa
Martyna: Korzystając z rozszerzonego algorytmu Euklidesa wyznaczyć odwrotność 16 modulo 103
3 lis 21:09
Mariusz:
103 = 6*16+7
7=103−6*16
16=2*7+2
2=16−2*7
7=3*2+1
1=7−3*2
1=7−3(16−2*7)
1=7*7−3*16
1=7*(103−6*16)−3*16
1=7*103−45*16
103−45 = 58
Odwrotność to
58
3 lis 21:25
Martyna: A dlaczego się to odejmuje pod koniec?
3 lis 22:16
ABC:
−45≡−45+103=58 (mod 103)
3 lis 22:20
Martyna: Oki, dziękuję
3 lis 22:25