Lösung - Euklidischer Algorithmus 02

Problem 1:
Finde mit Hilfe des erweiterten euklidischen Algorithmus die modulare Inverse von 15 mod 26 (also jene Zahl c mit 15.c mod 26 = 1

  I:    26    1     0
 II:    15    0     1      I -   II = III
III:    11    1    -1     II -  III =  IV
 IV:     4   -1     2    III - 2*IV =   V
  V:     3    3    -5     IV -    V =  VI
 VI:     1   -4     7      1 = -4*26 + 7*15

Die modulare Inverse von 15 mod 26 lautet 7 (15.7 mod 26 = 1).

Problem 2:
Finde mit Hilfe des erweiterten euklidischen Algorithmus die modulare Inverse von 5 mod 48 (also jene Zahl c mit 5.c mod 48 = 1)

  I:    48    1     0
 II:     5    0     1      I - 9*II = III
III:     3    1    -9     II -  III =  IV
 IV:     2   -1    10    III -   IV =   V
  V:     1    2   -19      1 = 2*48 - 19*5

Die modulare Inverse von 5 mod 48 lautet -19 + 48 = 29 (positiver Wert gesucht, daher -19 + 48 = 29, 5.29 mod 48 = 1)