Lösung - Euklidischer Algorithmus 01

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

Schritt 1: ggT(15,26)

26 = 1 * 15 +     11
         15 = 1 * 11 +     4
                  11 = 2 * 4 +     3
                           4 = 1 * 3 +     1
                                   3 = 3 * 1 + 0
ggT(15,26) = 1

Schritt2 - Umkehrung

1 = 4 - 1 * 3
            3 = 11 - 2 * 4
                         4 = 15 - 1 * 11
                                      11 = 26 - 1 * 15

Schritt 3 - Substitution

1 = 4 - (11 - 2 * 4)  ... substituiere 3 durch (11 - 2 * 4)
1 = 3 * 4 - 11
1 = 3 * (15 - 1 * 11) - 11  ... substituiere 4 durch (15 - 1 * 11)
1 = 3 * 15 - 4 * 11
1 = 3 * 15 - 4 * (26 - 1 * 15)  ... substituiere 11 durch (26 - 1 * 15)
und forme um
1 = 3 * 15 - 4 * 26 + 4 * 15
1 = 7 * 15 - 4 * 26

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)

Schritt 1: ggT(5,48)

48 = 9 * 5 +     3
         5 = 1 * 3 +     2
                 3 = 1 * 2 + 1
                         2 = 2 * 1 + 0

Schritt 2 - Umkehrung

1 = 3 - 2
        2 = 5 - 3
                3 = 48 - 9 * 5

Schritt 3 - Substitution

1 = 3 - (5 - 3)
1 = 2 * 3 - 5
1 = 2 * (48 - 9 * 5) - 5
1 = - 19 * 5 + 2 * 48 

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

Probe mit DERIVE

Probe


[ Schliessen ]