Teil 1

´133x -= 107 (mod 91)´ ´42x -= 16 (mod 91)´

´d = gcd(42,91)´

Euklidischer Algorithmus (Primfaktorzerlegung wäre schneller bei so kleinen Zahlen):

´91 = 2 * 42 + 7´ ´42 = 6 * 7 + 0´

´=> gcd(42, 91) = 7´

7 ∤ 16 => Es gibt keine Lösung

Teil 2

´133y -= 280 (mod 91)´ ´42y -= 7 (mod 91)´

´d = gcd(42, 91)´

Euklidischer Algorithmus (Primfaktorzerlegung wäre schneller bei so kleinen Zahlen):

´91 = 2 * 42 + 7´ ´42 = 6 * 7 + 0´

´=> gcd(42, 91) = 7´

´7 | 7 => "Es gibt eine Lösung"´

´42y -= 7 (mod 91)´ | :7 ´6x -= 1 (mod 13)´

Euklidischer Algorithmus:

´13 = 2 * 6 + 1´ ´6 = 6 * 1 + 0´

´=> -2 * 6 - 1 = -1 * 13´

´y -= -2 (mod 13)´ ´y -= 11 (mod 13)´

Lösungen sind alle ´y = 11 + z * 13 (z in ZZ)´

´y_1 -= 11 (mod 91)´ ´y_2 -= 24 (mod 91)´ ´y_3 -= 37 (mod 91)´ ´y_4 -= 50 (mod 91)´ ´y_5 -= 63 (mod 91)´ ´y_6 -= 76 (mod 91)´ ´y_7 -= 89 (mod 91)´

Teil 3

´97z -= 7 (mod 37)´ ´23z -= 7 (mod 37)´

´d = ggT(23, 37)´

Euklidischer Algorithmus (Teil 1):

´37 = 1 * 23 + 14´ ´23 = 1 * 14 + 9´ ´14 = 1 * 9 + 5´ ´9 = 1 * 5 + 4´ ´5 = 1 * 4 + 1´ ´4 = 4 * 1 + 0´

´ggT(23, 37) = 1´

Hilfskongruenz:

´23z_0 -= 1 (mod 37)´

Euklidischer Algorithmus (Teil 2):

´14 = 37 - 23´ ´9 = 23 - 14 = 23 - (37 - 23) = 2 * 23 - 37´ ´5 = 14 - 9 = (37 - 23) - (2 * 23 - 37) = 2 * 37 - 3 * 23´ ´4 = 9 - 5 = (2 * 23 - 37) - (2 * 37 - 3 * 23) = 5 * 23 - 3 * 37´ ´1 = 5 - 4 = (2 * 37 - 3 * 23) - (5 * 23 - 3 * 37) = 5 * 37 - 8 * 23´

´=> -8 * 23 - 1 = - 5 * 37´

´=> z_0 -= -8 (mod 37)´ ´z_0 -= 29 (mod 37)´

´z -= -8 * 7 = -56 -= 18 (mod 37)´