ich orientiere mich in folgendem an dem in https://de.wikipedia.org/wiki/Erweiterter_Euklidischer_Algorithmus#Allgemeine_mathematische_Grundlage beschriebenen sogenannten erweiterten euklidischen Algorithmus.
Der dort beschriebene Algorithmus kann folgendermaßen (handschriftlich) ausgeführt werden:
\( (a, b) = (1768, 71) \)
k = 0,
\( r_0 = a = 1768 \)
\( r_1 = b = 71 \)
\( s_0 = 1 \)
\( s_1 = 0 \)
k = 1: \( q_1 = r_0 \div r_1 = 1768 \div 71 = 24 \),
\( r_2 = r_0 - q_1 r_1 = 64 \),
\(s_2 = s_0 - q_1 s_1 = 1 \).
k = 2: \( q_2 = r_2 \div r_1 = 71 \div 64 = 1 \),
\( r_3 = r_1 - q_2 r_2 = 71 - 64 = 7 \),
\( s_3 = s_1 - q_2 r_2 = 0 - 1 = -1 \).
k = 3: \( q_3 = r_2 \div r_3 = 64 \div 7 = 9 \),
\( r_4 = r_2 - q_3 r_3 = 64 - 63 = 1 \),
\( s_4 = s_2 - q_3 s_3 = 1 - (-9) = 10 \).
k = 4: \( q_4 = r_3 \div r_4 = 7 \),
\( r_5 = r_3 - q_4 r_4 = 7 - (7 \cdot 1) = 0 \) (Abbruchkriterium),
\( s_5 = s_3 - q_4 s_4 = -1 - (7 \cdot 10) = -71 \).
Wir haben also \( r_4 = 1 \) und \( s_4=10 \). Es ergibt sich
\( t_4 = (r_4 - s_4 a) \div b = (1 - 10 \cdot 1768) \div 71 = - 249 \).
Schließlich gilt
\( 1 = s_4 a + t_4 b = 10 \cdot 1768 + (-249) \cdot 71 \).
Aus \( 1768 - 249 = 1519 \) ergibt sich mit \( b^{-1} = 1519 \) das multiplikative Inverse von \( b = 71 \) modulo 1768.
Probe: \( b b^{-1} - 1 = 71 \cdot 1519 - 1 = 107848 = 61 \cdot 1768 \) ist durch \( a = 1768 \) teilbar.
MfG
Mister
