Mathematik HTL 3, Schulbuch

242 Algebraische Strukturen 1055 Erstelle die Additionstafel und die Multiplikationstafel für  a. Z 3 und  b. Z 5  . Erläutere, wie man daraus leicht abliest, dass die Addition und die Multiplikation in diesen Ringen kommutativ sind. 1056 Erstelle die Additionstafel und die Multiplikationstafel für Z 6  . Erläutere, wie man aus der Multi­ plikationstafel leicht abliest, welche Elemente invertierbar sind. Bestimme diese Elemente. Der erweiterte euklidische Algorithmus Erinnern wir uns: Der größte gemeinsame Teiler (kurz: ggT) von zwei natürlichen Zahlen ist die größte Zahl, die beide teilt. Der ggT von zwei Zahlen kann mit dem euklidischen Algorithmus berechnet werden: Man ersetzt so lange die größere Zahl durch ihren Rest nach Division durch die kleinere, bis die kleinere Zahl die größere teilt. Dann ist diese kleinere Zahl der gesuchte ggT. Mit dem erweiterten euklidischen Algorithmus kann man zu je zwei natürlichen Zahlen a und b mit b ≠ 0 zwei ganze Zahlen u und v mit der Eigenschaft u·a + b·v = ggT(a, b) berechnen. Wir schreiben die richtigen Behauptungen I) a = 1·a + 0·b und II) b = 0·a + 1·b an. Dann dividieren wir a mit Rest durch b: a = m·b + r mit 0 ª r < b und ziehen links und rechts des Gleichheitszeichens das mFache von II von I ab und erhalten eine weitere richtige Behauptung III) r = (1 – m·0)·a + (0 – m)·b. Wir wiederholen dasselbe für II und III statt I und II, also für b und r statt für a und b und erhal­ ten die Behauptung IV. Weiter für III und IV, … solange, bis links vom Gleichheitszeichen 0 steht. Damit haben wir auf der linken Seite des Gleichheitszeichens den euklidischen Algorithmus für a und b ausgeführt. Die letzte Zahl auf der linken Seite, die nicht 0 ist, muss daher der ggT(a, b) sein. In dieser Zeile steht also ggT(a, b) = u·a + v·b, für ganze Zahlen u und v. Diese Zahlen sind die von uns gesuchten. Die Zahlen u und v sind nicht eindeutig bestimmt: Wenn u·a + v·b = ggT(a, b) ist, dann ist für alle ganzen Zahlen k auch (u + k·b)·a + (v – k·a)·b = ggT(a, b). Wenn u negativ ist, können wir k so groß wählen, dass u + k·b positiv ist. Es gibt also immer solche Zahlen u und v mit der Zusatzbedingung u º 0. 1057 Berechne ggT(493, 221) und zugleich ganze Zahlen u und v so, dass u·493 + v·221 = ggT(493, 221) ist. I) 493 = 1·493 + 0·221 II) 221 = 0·493 + 1·221 | I – 2·II 493 = 2·221 + 51, daher berechnen wir I – 2·II und erhalten: III) 51 = 1·493 – 2·221 | II – 4·III 221 = 4·51 + 17, daher berechnen wir II – 4·III und erhalten: IV) 17 = (‒ 4)·493 + 9·221 | III – 3·IV V) 0 = … Also ist ggT(221, 439) = 17 und die gesuchten Zahlen sind u = ‒4 und v = 9. Zur Probe berechnen wir: ‒ 4·493 + 9·221 = ‒1972 + 1982 = 17. Wenn u eine natürliche Zahl sein soll, ersetzen wir u = ‒4 durch ‒ 4 + 221 = 217 und v = 9 durch 9 – 493 = ‒484. Dann ist 17 = 217·493 – 484·221. B, D B, D erweiterter euklidischer Algorithmus B  ggb/tns s4k5ju den erweiterten euklidischen Algorithmus anwenden Nur zu Prüfzwecken – Eigentum des Verl gs öbv