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

Der Fall a < 0 kann auf den bereits behandelten Fall zurückgeführt werden.

\underline{(9.43) FOLG:} (Kleiner) Satz von Fermat, 1640 Für p ∈ IP und a ∈ ZZ mit p |̸ a gilt er erfüllt x = 6j

a^{p−1} ≡ 1 (mod p)

\underline{Bew:} : Nach (9.42) gilt a^{p} ≡ a (mod p) oder umgeschrieben

(⋆) [a]_{p}^{p} = [1]_{p}

Wegen p |̸ a sind p und a teilerfremd, so daß [a]_{p} nach (9.40) invertierbar ist. Multiplikation von (⋆) mit dem Inversen auf beiden Seiten ergibt die Behauptung.

Beispiel: 24^{12} ≡ 1 (mod 13) 24^{12} = 36520347436056576 ist eine 17–stellige Zahl.

24 ≡ −2 (mod 13) |^2
24^{2} ≡ 4 (mod 13) |^2
(⋆) 24^{4} ≡ 3 (mod 13) |^2
(⋆⋆) 24^{8} ≡ 9 (mod 13) Multiplikation von (⋆) und (⋆⋆)
24^{12} ≡ 1 (mod 13)

Eine Verallgemeinerung des Satzes von Fermat hat Euler 1760 gefunden: \underline{(9.44) SATZ:} Euler Für a ∈ ZZ und m ∈ IN mit ggT(a, m) = 1 gilt

a^{φ(m)} ≡ 1 (mod m).

Beispiel: 4^{10} = 4^{φ(15)} ≡ 1 (mod 15). Wegen φ(p) = p − 1 für eine Primzahl p ist der Satz von Fermat in dem Satz von Euler enthalten. Die Sätze von Fermat und Euler sind Grundlage für eine Reihe von Primzahltests, die leistungsfähiger als die bisher erwähnten sind.

Primzahltest Es gilt: p Primzahl ⟹ 2^{p} ≡ 2 (mod p) Die Umkehrung gilt i.a. nicht: Es ist 2^{341} ≡ 2 (mod 341) aber 341 = 11 · 31 ist zusammengesetzt. Wir nennen 341 eine Pseudoprimzahl (zur Basis 2). Gilt also 2^{n} ≡ 2 (mod n) für eine natürliche Zahl n, so können wir nicht schließen, daß n eine Primzahl ist. Gilt jedoch 2^{n} ≢ 2 (mod n), so ist n keine Primzahl. Ersetzen wir 2 durch eine beliebige Zahl b, so gilt für eine Primzahl p immer b^{p} ≡ b (mod p) und auch hier gilt nicht die Umkehrung. Gilt dagegen b^{n} ≢ b (mod n) für eine Zahl n ∈ IN,so ist n wieder keine Primzahl.

Es gilt 3^{341} ≢ 3 (mod 341) , woraus folgt, daß 341 keine Primzahl ist.

Testverfahren: Es soll untersucht werden, ob eine Zahl n ∈ IN eine Primzahl ist.

Dazu wählen wir uns eine “Testmenge“ B ⊆ IN und testen, ob für jedes b ∈ B die Kongruenz b^{n} ≡ b (mod n) gilt. Ist dies für ein b ∈ B nicht erfüllt, so ist n keine Primzahl, gilt dies jedoch für alle b ∈ B, so ist n mit einiger Wahrscheinlichkeit eine Primzahl. Es gibt jedoch Zahlen, die sich diesem Test vollständig entziehen. Dies sind zusammengesetzte Zahlen n (sog. Carmichael–Zahlen) mit b^{n} ≡ b (mod n) für alle b ∈ ZZ, z.B. n = 561.

Es handelt sich hierbei um einen probabilistischen Primzahltest.

Zum Abschluß wollen wir noch kurz den Chinesischen Restsatz behandeln. Es geht um das Problem, eine ganze Zahl zu bestimmen, die bei Division durch gewisse Zahlen vorgeschriebene Reste hat, z.B. ist x ∈ ZZ gesucht mit

x ≡ 1 (mod 5) , x ≡ 2 (mod 4)

Hier erfüllt x = 6 beide Kongruenzen, aber auch 26 = 6 + 4 · 5 und allgemein 6 + k · 6 (k ∈ ZZ)

\underline{(9.45) SATZ:} Chinesischer Restsatz (CRS)

Gegeben seien ganze Zahlen b_{1}, …, b_{r} und paarweise teilerfremde natürliche Zahlen m_{1}, …, m_{r}. Dann gibt es eine ganze Zahl x_{0} ∈ ZZ, die das folgende System von Kongruenzen simultan erfüllt:

(⋆) { x ≡ b_{1} (mod m_{1}) x ≡ b_{2} (mod m_{2}) ⋮ x ≡ b_{r} (mod m_{r})

Sind x_{0} und x′_{0} zwei Lösungen von (⋆), so folgt x ≡ x′ (mod m) , wobei m := m_{1}·m_{2}·. . .·m_{r} ist. Außerdem ist jedes Element aus der Restklasse [x_{0}]_{m} eine Lösung von (⋆).

\underline{Bew:} Es sei n_{k} := \frac{m}{m_{k}}. Es folgt n_{k} ∈ IN und ggT(m_{k}, n_{k}) = 1 für alle k = 1, 2, …, r. Dann

gibt es c_{k}, d_{k} ∈ ZZ mit 1 = m_{k}c_{k} + n_{k}d_{k} (EEA), und es ist

x_{0} := b_{1}n_{1}d_{1} + b_{2}n_{2}d_{2} + … + b_{r}n_{r}d_{r} ∈ ZZ

eine Lösung von (⋆). Für i ≠ k gilt nämlich n_{i} ≡ 0 (mod m_{k}) , also x_{0} ≡ b_{k}n_{k}d_{k} ≡ b_{k} (mod m_{k}) für alle k , da sich aus 1 = m_{k}c_{k} + n_{k}d_{k} die Kongruenz n_{k}d_{k} ≡ 1 (mod m_{k}) ergibt.

Der CRS ist die Grundlage für die modulare Arithmetik.

Modulare Addition

Wir wollen die beiden Zahlen a = 37 und b = 56 nach einem Verfahren addieren, das für große Zahlen schneller ist als die “normale Addition“. Dieses Beispiel soll nur das Verfahren erklären:

Wir wählen dazu eine Zahl m > a + b, hier etwa m = 140 , und stellen m als ein Produkt von paarweise teilerfremden Zahlen dar: m = 4 · 5 · 7. Wir bilden nun die Restklassen von 37 (bzw.

56) modulo 4,5 und 7 und addieren die entsprechenden Restklassen

37 ⟶  ([37]_{4}, [37]_{5}, [37]_{7}) = ([1]_{4}, [2]_{5}, [2]_{7})

+

56 ⟶  ([56]_{4}, [56]_{5}, [56]_{7}) = ([0]_{4}, [1]_{5}, [0]_{7})
93 ⟵ (⋆)  ([1]_{4}, [3]_{5}, [2]_{7})

(⋆) Mit dem CRS bestimmen wir eine Lösung x_{0} ∈ {0, 1, …, 139} des Systems x ≡ 1 (mod 4) x ≡ 3 (mod 5) x ≡ 2 (mod 7)

Das ergibt hier x_{0} = 93, und dies ist auch die Summe von 37 und 56. Berechnung von x_{0}: Mit der Bezeichnungsweise von (9.45) gilt: m_{1} = 4 , m_{2} = 5 , m_{3} = 7 , b_{1} = 1 , b_{2} = 3 , b_{3} = 2 , n_{1} = \frac{m}{m_{1}} = \frac{140}{4} = 35 , n_{2} = \frac{m}{m_{2}} = \frac{140}{5} = 28 , n_{3} = \frac{m}{m_{3}} = \frac{140}{7} = 20 ggT(4, 35) = 1 1 = 9 · 4 + (−1) · 35 d_{1} = −1 ggT(5, 28) = 1 1 = (−11) · 5 + 2 · 28 d_{2} = 2 ggT(7, 20) = 1 1 = 3 · 7 + (−1) · 20 d_{3} = −1 x_{0} = b_{1}n_{1}d_{1} + b_{2}n_{2}d_{2} + b_{3}n_{3}d_{3} = 1 · 35 · (−1) + 3 · 28 · 2 + 2 · 20 · (−1) = −35 + 168 − 40 = 93 Probe: 93 ≡ 1 (mod 4) , 93 ≡ 3 (mod 5) , 93 ≡ 2 (mod 7)

Modulare Multiplikation Berechne das Produkt 37 · 56 . Wähle dazu m = 3465 = 5 · 7 · 9 · 11.

37 ⟶ ([37]_{5}, [37]_{7}, [37]_{9}, [37]_{11}) = ([2]_{5}, [2]_{7}, [1]_{9}, [4]_{11})
×
56 ⟶ ([56]_{5}, [56]_{7}, [56]_{9}, [56]_{11}) = ([1]_{5}, [0]_{7}, [2]_{9}, [1]_{11})
2072 ⟵  ([2]_{5}, [0]_{7}, [2]_{9}, [4]_{11}) (⋆)

(⋆) Mit dem CRS bestimmen wir eine Lösung x_{1} ∈ {0, 1, …, 3464} des Systems x ≡ 2 (mod 5) x ≡ 0 (mod 7) x ≡ 2 (mod 9) x ≡ 4 (mod 11)

Das ergibt hier x_{1} = 2072, und dies ist auch das Produkt von 37 und 56.