Lösung - Euklidischer Algorithmus 01Problem 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: 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 |