§ 15. Spezielle Zahlen

(15.5) Lucas/Lehmer–Test für Mersenne’sche Primzahlen

Die Folge (u_{k})_{k∈ℕ_{0}} sei rekursiv definiert durch

u_{0} := 4 , u_{k+1} := u_{k}^{2} − 2 (k ≥ 0) .

Ist dann p eine ungerade Primzahl, so gilt

M_{p} = 2^{p} − 1 ∈ IP ⟺ u_{p−2} ≡ 0 (mod M_{p}) .

Dieser Test geht auf Edouard Lucas (1842–1891) zurück und wurde 1930 von Derrick Henry Lehmer (1905–1991) vereinfacht.

C) Pseudoprimzahlen

\underline{(15.6) LEMMA:} Ist a ∈ eine beliebige ganze Zahl, so gilt für jede Primzahl p ∈ IP

a^{p} ≡ a (mod p) .

\underline{(15.7) BEM:} a) Man kann mit (15.6) zeigen, daß eine Zahl nicht prim ist: Gibt es nämlich für n ∈ ℕ ein b ∈ ℤ mit b^{n} ≢ b mod n, so ist n \underline{keine} Primzahl.

b) Insbesondere gilt 2^{n} ≡ 2 (mod n) . Zu Zeiten Fermat’s glaubte man wohl, daß Zahlen n mit dieser Eigenschaft prim sind. Dies ist nicht verwunderlich, denn

∀ n ∈ ℕ : 2 ≤ n ≤ 340 ∧ 2^{n} ≡ 2 (mod n) ⟹ n ∈ IP .

Es gilt aber 2^{341} ≡ 2 (mod 341) und 341 = 11 · 31 ∉ IP . (Immerhin hat die Zahl 2^{341} 103 Dezimalstellen!)

\underline{(15.8) DEF:} Eine zusammengesetzte natürliche Zahl n ≥ 2 heißt Pseudoprimzahl , wenn 2^{n} ≡ 2 (mod n) gilt.

\underline{(15.9) BEM:} a) n ∈ ℕ , n ≥ 2 : 2^{n} ≡ 2 (mod n) ⟺ n prim pder pseudoprim.

b) 341, 561, 645 sind alle Pseudoprimzahlen ≤ 1000 . Diese sind alle ungerade. Pseudoprimzahlen kommen viel seltener vor als Primzahlen:

n  π(n) Anz.Pseudopr. ≤ n Anz.Carm Z. ≤ n
10^{3}  168  3  1
10^{6} 78 498  247  42

c) 161 038 = 2 · 73 · 1103 ist eine \underline{gerade} Pseudoprimzahl.

d) Frage: Gibt es unendlich viele Pseudoprimzahlen? Antwort: ja (Beweis später) .

\underline{(15.10) DEF:} Sei b ∈ ℤ.Eine zusammengesetzte natürliche Zahl n ≥ 2 heißt Pseudoprimzahl zur Basis b, wenn b^{n} ≡ b (mod n) gilt. \underline{Beispiele:} Pseudoprimzahlen zur Basis 2 sind gerade die vorher definierten Pseudoprimzahlen. 341 ist pseudoprim zur Basis 2, nicht aber zur Basis 3 . 91 ist pseudoprim zur Basis 3 , 15 ist pseudoprim zur Basis 4 . \underline{(15.11) LEMMA:} Für die Zahl 561 gilt

a) 561 ist nicht prim

b) b^{561} ≡ b (mod 561) ∀ b ∈ ℤ. \underline{(15.12) DEF:} Eine zusammengesetzte natürliche Zahl n ≥ 2 heißt Carmichael–Zahl , wenn

b^{n} ≡ b (mod n)

für alle b ∈ ℤ gilt. Robert Daniel Carmichael (1879–1967), US–amerikanischer Mathematiker \underline{(15.13) BEM:} a) Beispiele für Carmichael–Zahlen: 561 = 3·11·17 , 172 081 = 7·13·31·61 .

b) 3^{341} ≢ 3 mod 341 , 3^{645} ≢ 3 mod 645 . 341 und 645 sind also keine Carmichael Zahlen .

c) n ≥ 2 zusammengesetzt: n Carmichael–Zahl ⟺ b^{n} ≡ b (mod n) ∀ b ∈ {2, 3, …, n−1} d) Carmichael–Zahlen kommen viel seltener als Pseudoprimzahlen vor (s. Tabelle).

e) Es gibt unendlich viele Carmichael Zahlen (Pommerance/Alford/Granville, 1994) . (15.14) Pseudoprimzahltest Seien n ≥ 3 eine ungerade natürliche Zahl und T = {2, 3, …, n − 1}. Gibt es ein b ∈ T mit b^{n} ≢ b mod n, so ist n \underline{nicht} prim. Gilt dagegen b^{n} ≡ b (mod n) für r zufällig aus T ausgewählte Zahlen, so ist n mit einer gewissen Wahrscheinlichkeit prim. Allerdings versagt das Verfahren, wenn n eine Carmichael Zahl ist. \underline{(15.15) LEMMA:} Für n ∈ ℕ gilt: 2^{n} ≡ 2 (mod n) ⟹ 2^{M_{n}} ≡ 2 (mod M_{n}) . \underline{(15.16) KOROLLAR:} a) n ∈ ℕ pseudoprim ⟹ M_{n} = 2^{n} − 1 pseudoprim.

b) Es gibt unendlich viele Pseudoprimzahlen .

c) p ∈ IP ⟹ M_{p} ist entweder prim oder pseudoprim. \underline{(15.17) BEM:} Die n–te Fermat’sche Zahl F_{n} = 2^{2^{n}} + 1 (n ∈ ℕ_{0}) ist entweder prim oder pseudoprim.