Chr.Nelius , Mathematik für Informatiker I, (WS 2000/01) 15.1.2001

\underline{(9.30) SATZ:} Für n ∈ IN, n ≥ 2 sind folgende Aussagen äquivalent:

a) n ist eine Primzahl

b) n besitzt keinen Teiler t ∈ IN mit 2 ≤ t ≤ ⌊\sqrt{n}⌋

c) n besitzt keinen Primteiler p mit p ≤ ⌊\sqrt{n}⌋.

\underline{(9.31) BEM:} Primzahltest

Es soll eine Zahl n ∈ IN, n ≥ 2 auf Primzahleigenschaft getestet werden:

a) Untersuche, ob eine der Zahlen 2, 3, …, ⌊\sqrt{n}⌋ ein Teiler von n ist. Wenn ja, ist n keine Primzahl, wenn nein, so ist n nach (9.30) prim. In diesem Falle sind ⌊\sqrt{n}⌋ − 1 Divisionen erforderlich, problematisch für große n.

b) Untersuche, ob eine der Primzahlen ≤ ⌊\sqrt{n}⌋ ein Teiler von n ist. Aufwand, falls n prim: π(⌊\sqrt{n}⌋) Divisionen. Problematisch: Erstellen von Primzahllisten. Dafür gibt es Siebverfahren, in der einfachsten Form: Sieb von Eratosthenes.

c) Sei IP′ := {2, 3, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31, 35, 37, … }. Diese Menge besteht aus 2,3 und allen Zahlen der Form 6k − 1, 6k + 1 (k ∈ IN). Nach Aufgabe 39 gilt IP ⊆ IP′. Nach (9.30) gilt

n ∈ IP ⟺ ∀ t ∈ IP′, t ≤ ⌊\sqrt{n}⌋ : t |̸ n.

Im Gegensatz zur Menge aller Primzahlen ≤ ⌊\sqrt{n}⌋ läßt sich die Menge IP′ leicht bilden: beginnend mit 5 addiere abwechselnd 2 und 4. Im Falle daß n Primzahl ist, sind ungefähr ⌊\sqrt{n}⌋/3 Divisionen erforderlich.

In allen Fällen erhält man für “große“ n kein Ergebnis in vernünftiger Zeit. Effizientere Methoden erfordern einen viel größeren mathematischen Aufwand.

\underline{(9.32) BEM:} Primfaktorzerlegung

Um die Primfaktorzerlegung einer natürlichen Zahl n ≥ 2 zu finden, gehe man folgendermaßen vor: Versuche, einen Teiler t von n mit 2 ≤ t ≤ ⌊\sqrt{n}⌋ zu bestimmen. Gibt es den nicht, so ist n eine Primzahl und die Primfaktorzerlegung von n ist n. Gibt es ihn dagegen, so verfahre mit t und \frac{n}{t} ∈ IN analog. Nach endlich vielen Schritten ist n als Produkt von Primzahlen dargestellt.

\underline{(9.33) DEF:} Seien a, b ∈ ZZ und m ∈ IN. a heißt kongruent zu b modulo m, in Zeichen a ≡ b (mod m) , wenn gilt

a mod m = b mod m

Die hierdurch definierte Relation auf ZZ heißt Kongruenzrelation modulo m.

2 ≡ 5 (mod 3) 3 ≢ 6 (mod 4)

\underline{(9.34) BEM:} a ≡ b (mod m) ⟺ m|a − b

\underline{(9.35) SATZ:} Für jedes m ∈ IN ist die Kongruenzrelation modulo m eine Äquivalenzrelation auf ZZ. Die Äquivalenzklassen nach dieser Relation heißen Restklassen modulo m. Mit ZZ_{m} wird die Menge aller Restklassen modulo m bezeichnet.

S. Beispiel 12 in §4, Def (4.8) und (4.9)

[a]_{m} = { x | x ∈ ZZ, x ≡ a (mod m) } ⊆ ZZ Restklasse von a modulo m. In einer Restklasse modulo m liegen alle ganzen Zahlen, die bei Division durch m denselben Rest haben.

[2]_{3} = { x | x ∈ ZZ, x ≡ 2 (mod 3) } ⊆ ZZ ist die Menge aller ganzen Zahlen, die bei Division durch 3 den Rest 2 haben. [2]_{3} = { …, −7, −4, −1, 2, 5, 8, 11, … }

[0]_{5} = { x | x ∈ ZZ, x ≡ 0 (mod 5) } ⊆ ZZ ist die Menge aller ganzen Zahlen, die bei Division durch 5 den Rest 0 haben, die also durch 5 teilbar sind.

[0]_{2} = { x | x ∈ ZZ, x ≡ 0 (mod 2) } Menge der geraden ganzen Zahlen.

[1]_{2} = { x | x ∈ ZZ, x ≡ 1 (mod 2) } Menge der ungeraden ganzen Zahlen.

Nach (4.10b) gilt [a]_{m} = [b]_{m} ⟺ a ≡ b (mod m)

\underline{(9.36) SATZ:} Es gilt ZZ_{m} = \{ [0]_{m}, [1]_{m}, …, [m − 1]_{m} \} und |ZZ_{m}| = m.

\underline{Bew:} 0, 1, …, m − 1 sind die möglichen Reste bei Division einer ganzen Zahl durch m.

Für das Rechnen mit Kongruenzen gelten die folgenden Regeln:

\underline{(9.37) SATZ:} Gelte a ≡ b (mod m) und c ≡ d (mod m) . Dann folgt:

a) a + c ≡ b + d (mod m) b) a · c ≡ b · d (mod m)

c) a^{k} ≡ b^{k} (mod m) ∀ k ∈ IN_{0}.

Anwendung: Teilbarkeitsregel für 3:

Es gilt 10 ≡ 1 (mod 3) , woraus nach (9.35c) 10^{k} ≡ 1 (mod m) für alle k ∈ IN_{0} folgt. Sei

n = ∑_{k=0}^{r} a_{k}10^{k} eine natürliche Zahl in Dezimaldarstellung. Dann ergibt sich n ≡ ∑_{k=0}^{r} a_{k} (mod m)

(rechts steht die Quersumme von n).

Also: 3|n ⟺ n ≡ 0 (mod 3) ⟺ ∑_{k=0}^{r} a_{k} ≡ 0 (mod 3) ⟺ 3 | ∑_{k=0}^{r} a_{k}

Fazit: Eine ganze Zahl ist genau dann durch 3 teilbar, wenn ihre Quersumme durch 3 teilbar ist. Es gibt weitere einfache Teilbarkeitsregeln, etwa für die Teilbarkeit durch 2,4,5,8,9,11 .

\underline{(9.38) SATZ:} Auf der Menge ZZ_{m} aller Restklassen modulo m lassen sich eine Addition und eine Multiplikation erklären, so daß ZZ_{m} ein kommutativer Ring ist. Diese Rechenoperationen sind definiert durch:

[a]_{m} + [b]_{m} := [a + b]_{m} , [a]_{m} · [b]_{m} := [a · b]_{m}

[2]_{5} + [4]_{5} := [2 + 4]_{5} = [6]_{5} = [1]_{5} , [4]_{6} · [5]_{6} = [4 · 5]_{6} = [20]_{6} = [2]_{6}

Für die Addition gelten die A_{0}) bis A_{4}) aus (1.1) entsprechenden Eigenschaften. Das Nullelement ist in diesem Fall [0]_{m} , und das zu [a]_{m} negative Element ist die Restklasse [−a]_{m}. Für die Multiplikation gelten die M_{0}) bis M_{3}) entsprechenden Eigenschaften. Das Einselement ist hier [1]_{m}. Das Analoge zu M_{4}) gilt i.a. nicht, jedoch in Spezialfällen, wie wir gleich sehen werden. Das Distributive Gesetz ist wieder gültig.

Man nennt ZZ_{m} einen kommutativen Ring (IR hatten wir als Körper bezeichnet).

Für die Addition und Multiplikation auf ZZ_{m} können wir sog. Verknüpfungstafeln aufstellen, z.B. für ZZ_{3} oder ZZ_{4}.

\underline{(9.39) DEF:} Eine Restklasse [a]_{m} ∈ ZZ_{m} heißt invertierbar (bzgl. der Multiplikation), wenn es eine Restklasse [b]_{m} ∈ ZZ_{m} gibt mit [a]_{m} · [b]_{m} = [1]_{m} . [b]_{m} heißt dann das Inverse von [a]_{m}.

\underline{(9.40) SATZ:} Eine Restklasse [a]_{m} ∈ ZZ_{m} ist genau dann invertierbar, wenn a und m teilerfremd sind. Das Inverse läßt sich mit Hilfe des EEA berechnen.

\underline{Bew:} Es sei [a]_{m} invertierbar. Dann gibt es b ∈ ZZ mit [1]_{m} = [a]_{m} · [b]_{m} = [a · b]_{m} , d.h.es gilt ab ≡ 1 (mod m), oder m|1−ab. Folglich gibt es ein c ∈ ZZ mit mc = 1−ab oder mc+ab = 1. Sei nun g := ggT(a, m). Aus g|a und g|m folgt g|mc + ab, also g|1 und damit g = 1.

Gelte umgekehrt ggT(a, m) = 1. Dann existieren nach (9.12) x, y ∈ ZZ mit 1 = xa + ym. Für die zugehörigen Restklassen modulo m bedeutet dies:

[1]_{m} = [xa + ym]_{m} = [xa]_{m} + [ym]_{m} = [xa]_{m} + [0]_{m} = [x]_{m}[a]_{m}

Folglich ist [x]_{m} die inverse Restklasse zu [a]_{m} und x läßt sich mit dem EEA berechnen.

\underline{(9.41) FOLG:} Ist p eine Primzahl, so ist jede Restklasse [a]_{p} ≠ [0]_{p} invertierbar, d.h. ZZ_{p} ist ein Körper.

\underline{Bew:} ZZ_{p} = \{ [0]_{p}, [1]_{p}, …, [p − 1]_{p} \}. Für k = 1, 2, …, p − 1 ist ggT(k, p) = 1 , so daß die Restklassen [1]_{p}, [2]_{p}, …, [p − 1]_{p} alle invertierbar sind. Dies sind aber alle von [0]_{p} verschiedenen Restklassen, so daß auch das Analoge von M_{4}) aus (1.1) gilt. Daher ist ZZ_{p} ein Körper.

ZZ_{2}, ZZ_{3}, ZZ_{5}, ZZ_{7} sind Körper, ZZ_{4}, ZZ_{6}, ZZ_{8} sind keine Körper.

19.1.2001

\underline{(9.42) SATZ:} Es sei p eine Primzahl. Dann gilt für alle a ∈ ZZ

a^{p} ≡ a (mod p)

\underline{Bew:} : Wir beweisen die Behauptung für a ≥ 0 durch vollständige Induktion:

\underline{a = 0} klar

\underline{a ⟶ a + 1} Nach der binomischen Formel (7.11) gilt

(a + 1)^{p} = \binom{p}{0}a^{p} + \binom{p}{1}a^{p−1} + \binom{p}{2}a^{p−2} + … + \binom{p}{p − 1}a + \binom{p}{p}

Nach Aufg. 41 sind die Binomialkoeffizienten \binom{p}{1} bis \binom{p}{p−1} alle durch p teilbar, also kongruent 0 modulo p. Folglich

(a + 1)^{p} ≡ \binom{p}{0}a^{p} + \binom{p}{p} ≡ a^{p} + 1 ≡^{(IV)} a + 1 (mod p)