Inhaltsverzeichnis

1  Das Rechnen mit Resten - nicht nur für Kinder  3

2  Exkurs: Algebraische Strukturen  3

2.1  Gruppen  4

2.2  Ringe und Körper  5

3  Kongruenz- und Restklassenrechnung  6

3.1  Der Begriff der Kongruenz  6

3.2  Der Begriff der Restklasse  7

3.3  Addition und Multiplikation modulo m  8

3.4  Restklassenringe  10

3.5  Rechenbeispiele  11

3.5.1  Ein kleines Geburtstags-Experiment  11

3.5.2  Die letzten Dezimalstellen großer Zahlen  12

3.5.3  Die Fermat-Zahl F 5  13

4  Zwei ausgewählte Anwendungen  13

4.1  Teilbarkeitsregeln bis 15  13

4.2  Der Fermatsche Primzahltest  17

5  Ausblick: Restklassen in der Kryptographie  21

6  Anhang  23

Element zu x ∈ R \ {0} ist 1 (denn x · 1 = 1 · x = 1). Davon abgeleitet nennt man das neutrale Element x x x

1 Allgemein beschäftigt sich die Algebra mit der Untersuchung solcher Strukturen.

2 D.h., dass die Verknüpfungen zweier beliebiger Elemente aus G wieder in G liegen.

3 Es reicht sogar, hier und in (2.1.3) nur die linken Seiten der Gleichungen zu fordern, da aus ihnen schon die rechten

folgen [BA] 2 . Das soll hier jedoch nicht bewiesen werden.

1. Das neutrale Element e ist eindeutig bestimmt, denn für zwei neutrale Elemente e und ´ e gilt nach

e = ´ e ◦ e = e. Ebenso ist das inverse Element zu einem bestimmten a ∈ G eindeutig, (2.1.2) ´

a −1 zu a gilt: a −1 (2.1.2) = e ◦ a −1 (2.1.3) a −1 ◦ a) ◦ a −1 (2.1.1) denn für zwei inverse Elemente a −1 und ´ = ( ´ = (2.1.3) (2.1.2) a −1 ◦ (a ◦ a −1 ) ´ = ´ = ´ a −1 ◦ e a −1 .

2. Das inverse Element des inversen Elements zu a ist a selbst, also (a −1 ) −1 = a, denn sowohl (a −1 ) −1 als auch a sind zu a −1 invers ((a −1 ) −1 ◦ a −1 = e und a ◦ a −1 = e), sie müssen also nach

Eigenschaft 1 identisch sein.

0 · x = (0 + 0) · x = 0 · x + 0 · x, weshalb 0 · x additiv neutral bzw. gleich 0 sein muss.

4 Wie in 2.1 könnte man an dieser Stelle eine Reihe von Folgerungen aus den Ring-/Körperaxiomen machen, und würden

zu dem Ergebnis gelangen dass man in allen Ringen bzw. Körpern im Großen und Ganzen so rechnen kann, wie man

es aus den ganzen bzw. den rationalen Zahlen gewohnt ist (siehe z.B. [FG] 3 ). Das wäre jedoch für die Zwecke dieser

Arbeit ein zu weit abschweifendes und umfangreiches Unterfangen.

5 Genaueres in der 2. Anmerkung zum Java-Quelltext im Anhang (Beweis mit Hilfe der Kongruenzschreibweise!)

• reflexiv, d.h. a ≡ a mod m stets, da m | (a − a).

• symmetrisch, d.h., aus a ≡ b mod m folgt b ≡ a mod m, da m mit a − b auch b − a = −(a − b) teilt.

• transitiv, d.h., aus a ≡ b mod m und b ≡ c mod m folgt schon a ≡ c mod m, da m mit a − b und b − c auch deren Summe (a − b) + (b − c) = a − c teilt bzw. da, wenn a und b und ebenso b und c den selben Rest bei Division durch m lassen, a und c auch den selben Rest lassen.

6 lat. congruens: übereinstimmend, modus: Maß [LA]. Kongruent modulo 7 meint wörtlich also gleich, gemessen an 7.

7 Das bedeutet das gleiche [BP] 5 , ist aber oft schöner nachzuweisen.

Additionstabelle modulo 4 Multiplikationstabelle modulo 4

a ⊕ ´ b = ´ a + ´ b. Wegen a ≡ ´ a und b ≡ ´ b mod m ist nach der Rechenregel aber auch a + b ≡ ´ a + ´ b ´

mod m und damit a + b = ´ a + ´ b. Beispielsweise ist 7 ≡ 2 mod 5 und 8 ≡ 3 mod 5, also 7 = 2