"Teil 1\n\n´133x -= 107 (mod 91)´\n´42x -= 16 (mod 91)´\n\n´d = gcd(42,91)´\n\nEuklidischer Algorithmus (Primfaktorzerlegung wäre schneller bei so kleinen Zahlen):\n\n´91 = 2 \* 42 + 7´\n´42 = 6 \* 7 + 0´\n\n´=> gcd(42, 91) = 7´\n\n7 ∤ 16 => Es gibt keine Lösung\n\n\nTeil 2\n\n´133y -= 280 (mod 91)´\n´42y -= 7 (mod 91)´\n\n´d = gcd(42, 91)´\n\nEuklidischer Algorithmus (Primfaktorzerlegung wäre schneller bei so kleinen Zahlen):\n\n´91 = 2 \* 42 + 7´\n´42 = 6 \* 7 + 0´\n\n´=> gcd(42, 91) = 7´\n\n´7 | 7 => "Es gibt eine Lösung"´\n\n´42y -= 7 (mod 91)´ | :7\n´6x -= 1 (mod 13)´\n\n\nEuklidischer Algorithmus:\n\n´13 = 2 \* 6 + 1´\n´6 = 6 \* 1 + 0´\n\n´=> -2 \* 6 - 1 = -1 \* 13´\n\n´y -= -2 (mod 13)´\n´y -= 11 (mod 13)´\n\nLösungen sind alle ´y = 11 + z \* 13 (z in ZZ)´\n\n´y\_1 -= 11 (mod 91)´\n´y\_2 -= 24 (mod 91)´\n´y\_3 -= 37 (mod 91)´\n´y\_4 -= 50 (mod 91)´\n´y\_5 -= 63 (mod 91)´\n´y\_6 -= 76 (mod 91)´\n´y\_7 -= 89 (mod 91)´\n\n\nTeil 3\n\n´97z -= 7 (mod 37)´\n´23z -= 7 (mod 37)´\n\n´d = ggT(23, 37)´\n\nEuklidischer Algorithmus (Teil 1):\n\n´37 = 1 \* 23 + 14´\n´23 = 1 \* 14 + 9´\n´14 = 1 \* 9 + 5´\n´9 = 1 \* 5 + 4´\n´5 = 1 \* 4 + 1´\n´4 = 4 \* 1 + 0´\n\n´ggT(23, 37) = 1´\n\nHilfskongruenz:\n\n´23z\_0 -= 1 (mod 37)´\n\n\nEuklidischer Algorithmus (Teil 2):\n\n´14 = 37 - 23´\n´9 = 23 - 14 = 23 - (37 - 23) = 2 \* 23 - 37´\n´5 = 14 - 9 = (37 - 23) - (2 \* 23 - 37) = 2 \* 37 - 3 \* 23´\n´4 = 9 - 5 = (2 \* 23 - 37) - (2 \* 37 - 3 \* 23) = 5 \* 23 - 3 \* 37´\n´1 = 5 - 4 = (2 \* 37 - 3 \* 23) - (5 \* 23 - 3 \* 37) = 5 \* 37 - 8 \* 23´\n\n´=> -8 \* 23 - 1 = - 5 \* 37´\n\n´=> z_0 -= -8 (mod 37)´\n´z_0 -= 29 (mod 37)´\n\n´z -= -8 \* 7 = -56 -= 18 (mod 37)´"