Mathematik HTL 3, Schulbuch

238 5.2 Restklassenringe Ich lerne Rechenregeln für das Rechnen mit Resten kennen und ich lerne sie anzuwenden. Ich lerne einige Ringe und Körper mit endlich vielen Elementen kennen. Ich lerne den erweiterten euklidischen Algorithmus kennen und ich lerne damit die inversen Elemente bezüglich der Multiplikation in Z n zu berechnen. Rechnen mit Resten Welchen Rest erhalten wir, wenn wir 7 10 mit Rest durch 11 dividieren? Es wäre sehr mühsam, zuerst 7 10 zu berechnen und diese riesengroße Zahl dann mit Rest durch 11 zu dividieren. Wir hätten dann viel mehr berechnet, als gefragt war. Es sollte ja nur der Rest von 7 10 berechnet werden und nicht 7 10 selbst. Wir überlegen uns, wie das einfacher geht. Erinnern wir uns an den Satz über die Division mit Rest von natürlichen Zahlen: Zu je zwei natürlichen Zahlen a und b mit b ≠ 0 gibt es eindeutig bestimmte natürliche Zahlen m und r so, dass a = m·b + r und r < b ist. Die Zahl m heißt ganzzahliger Quotient und die Zahl r heißt Rest von a nach Division durch b. Beispiel: 49 = 4·11 + 5, also ist 4 der ganzzahlige Quotient und 5 der Rest von 49 nach Division durch 11. Für natürliche Zahlen a und b mit b ≠ 0 bezeichnen wir den Rest von a nach Division durch b mit a mod b (sprich: „a mod b“ oder „a modulo b“). Diese Zahl ist eine natürliche Zahl, die kleiner als b ist. Der Rest a mod b ändert sich nicht, wenn man zu a ein Vielfaches von b addiert: Für alle natürlichen Zahlen t ist (a + t·b) mod b = a mod b . Wenn a eine negative ganze Zahl ist, dann wählen wir ein Vielfaches t · b von b so, dass a + t·b > 0 ist und definieren a mod b als den Rest von a + t · b nach Division durch b. Beispiele: � 7 mod 4 = 3 � 67 mod 99 = 67 � ‒17 mod 5 = (‒17 + 4·5) mod 5 = 3 mod 5 = 3 Für das Rechnen mit Resten gelten die folgenden Regeln: Für natürliche Zahlen a, b, c mit b ≠ 0 gilt: (a + c) mod b = ((a mod b) + (c mod b)) mod b Der Rest der Summe ist der Rest der Summe der Reste. (a – c) mod b = ((a mod b) – (c mod b)) mod b Der Rest der Differenz ist der Rest der Differenz der Reste. (a·c) mod b = ((a mod b)·(c mod b)) mod b Der Rest des Produktes ist der Rest des Produktes der Reste. Falls c eine natürliche Zahl ist, gilt: ​a​ c ​mod b = (a mod b​)​ c ​mod b Der Rest der Potenz ist der Rest der Potenz des Restes. Diese Regeln für das Rechnen mit Resten können direkt nachgeprüft werden. Satz über die Division mit Rest natürlicher Zahlen  ggb 8yp8tw a mod b Regeln für das Rechnen mit Resten Nur zu Prüfzwecken – Eigentum es Verlags öbv