Mathematik HTL 3, Schulbuch

243 5.2 Restklassenringe Wenn n eine Primzahl ist, dann ist Z n mit + n und × n ein Körper. Die zu a inverse Zahl in Z n kann wie folgt berechnet werden: Berechne mit dem dem erweiterten euklidischen Algorithmus ganze Zahlen u und v so, dass u·n + v·a = ggT(n, a) ist. Dann ist v mod n die zu a inverse Zahl in Z n  . Denn: Weil n eine Primzahl ist und a < n ist, muss ggT(a, n) = 1 sein. Daher ist (u·n + v·a) mod n = 1. Wegen 1 = (u·n + v·a) mod n = (u mod n)(n mod n) + (v mod n)(a mod n) = = ((v mod n)·a) mod n = (v mod n) × n  a ist (v mod n) × n a = 1. 1058 Berechne die zu 13 inverse Zahl in Z 17  . Die Zahl 17 ist eine Primzahl, also ist die Aufgabe lösbar. Wir wenden den erweiterten euklidischen Algorithmus auf 17 und 13 an: I) 17 = 1·17 + 0·13 II) 13 = 0·17 + 1·13 | I – II III) 4 = 1·17 – 1·13 | II – 3·III IV) 1 = (‒ 3)·17 + 4·13 | III – 4·IV V) 0 = … Daher ist 4× 17  13 = 1, also ist 4 die zu 13 inverse Zahl in Z 17  . 1059 Gegeben sind die Zahlen a und b. Berechne mit dem euklidischen Algorithmus Zahlen u und v so, dass ggT(a, b) = u·a + v·b ist. a. a = 34; b = 26 b. a = 301; b = 499 c. a = 711; b = 339 d. a = 395; b = 1 005 1060 Begründe: Wenn a und b natürliche Zahlen sind und u, v ganze Zahlen so, dass u·a + v·b = ggT(a, b) ist, dann haben u und v verschiedene Vorzeichen. 1061 Begründe: Für natürliche Zahlen a und b gibt es ganze Zahlen u und v mit u º 0 so, dass u·a + v·b = ggT(a, b) ist. Ermittle die Lösungen von Aufgabe 1059 so, dass sie diese Eigenschaft haben. 1062 Berechne mithilfe des erweiterten euklidischen Algorithmus die zu 4 inverse Zahl in Z 7  . 1063 Ermittle mithilfe des erweiterten euklidischen Algorithmus die zu 68 inverse Zahl in Z 101  . 1064 Berechne mithilfe des erweiterten euklidischen Algorithmus eine natürliche Zahl u so, dass u·a mod p = 1 ist. a. a = 6; p = 17 b. a = 15; p = 23 c. a = 12; p = 47 d. a = 36; p = 59 1065 Berechne mithilfe des erweiterten euklidischen Algorithmus das zu a inverse Element in Z n  . a. a = 12; n = 13 b. a = 16; n = 17 c. a = 44; n = 45 d. a = 1 036; n = 1 037 1066 Sieh dir noch einmal deine Ergebnisse von Aufgabe 1065 an. Kannst du einen Zusammenhang erkennen? Dokumentiere deine Beobachtungen. 1067 Wenn ggT(a, n) = 1 ist, kann man mit dem erweiterten euklidischen Algorithmus auch dann das zu a inverse Element in Z n finden, wenn n keine Primzahl ist. Begründe das. 1068 Berechne eine Zahl b in Z 26 so, dass f: Z 26 ¥ Z 26  , z ¦ b× 26  z die Umkehrfunktion von f: Z 26 ¥ Z 26  , z ¦ a× 26  z ist. a. a = 9 b. a = 19 c. a = 25 die Inverse einer Zahl in Z n berechnen B inverse Zahl in Z 17 berechnen  ggb/tns fd6vq6 B D D B B B B C D B N r zu Prüfzwecken – Eigentum des Verlags öbv