3.5.1 PRIMZAHLERZEUGUNG UND DER SATZ VON WILSON

Gehen wir noch einmal auf die Bemerkung 2 oben ein. Es gib jedes für alle 0<a<p genau ein Inverses im selben Bereich. Dabei ist trivialerweise 1 selbstinvers, d.h. 1×1º 1 mod p. Gibt es ein weiteres Selbstinverses? Dazu untersuchen wir die Gleichung a^2º 1 mod p:
a^2º 1 Û a²-1º 0 Û (a-1)(a+1)º 0 Û a-1º 0 Ú a+1º 0 mod p (nach K9)
a-1º 0 führt zu aº 1 und damit wegen a<p zu a=1; a+1º 0 führt zu aº -1º p-1 mod p
Damit ist p-1 als zweites und letztes Selbstinverses enttarnt. Im Produkt
(p-1)!=1× 2× 3× 4× × × (p-2)× (p-1) hat also jeder der Faktoren von 2 bis p-2 einen inversen Partner. Faßt man diese jeweils zusammen und ersetzt sie durch 1, so bleibt

(p-1)!º p-1º -1 mod p Û pï (p-1)!+1 (Voraussetzung: p prim!!)

Es gilt sogar die Umkehrung: Ist nämlich p nicht prim, also p=s× t mit s>1, so enthält (p-1)! sicher die Faktoren s und t. Dann gilt aber (p-1)!+1º 1 mod p, d.h. die "Chose" funktioniert nur für Primzahlen. Der Sachverhalt hat auch einen Namen:

SATZ 3.5 Satz von Wilson: p prim Û pï (p-1)!+1

Dieser bemerkenswerte Satz, der ein Kriterium für Primalität mit nur einer Division liefert, ist leider nicht sehr benutzerfreundlich: 
Schon für die Primzahl 71 hat die zu prüfende Zahl 70!+1 mehr als 99 Stellen. Für kleine Zahlen kann man ihn aber verifizieren: 5ï4!+1=25 , aber nicht 6ï5!+1=121. Überprüfe selbst für 7, 8, 9, 10 und 11.

Die Gesetzmäßigkeiten der Primzahlreihe hat die Mathematiker von jeher fasziniert. Zagier schreibt dazu: "Es gibt zwei Tatsachen über die Verteilung der Primzahlen,...Die eine ist, dass die Primzahlen, trotz ihrer einfachen Definition und Rolle als Bausteine der natürlichen Zahlen, zu den willkürlichsten, widerspenstigsten Objekten gehören, die der Mathematiker überhaupt studiert. Sie wachsen wie Unkraut unter den natürlichen Zahlen, scheinbar keinem anderen Gesetz als dem Zufall unterworfen, und kein Mensch kann voraussagen, wo wieder eine sprießen wird, noch einer Zahl ansehen, ob sie prim ist oder nicht. Die andere Tatsache ist viel verblüffender, denn sie besagt just das Gegenteil - dass die Primzahlen die ungeheuerste Regelmäßigkeit aufzeigen, dass sie durchaus Gesetzen gehorchen, und dies mit fast peinlicher Genauigkeit."

In der folgenden Aufgabe sollen einige Versuche der Primzahlerzeugung untersucht werden:

AUFGABE 3.52 Untersuche jeweils den angedeuteten Ansatz zur Primzahlerzeugung:

Die Folge in d) entsteht dadurch, dass man in der n Zeile dann zwischen zwei Glieder der vorherigen Zeile die Zahl n setzt, wenn die Summe zweier benachbarter Glieder n ergibt. Dann wird die Anzahl der Glieder in einer Zeile betrachtet. (Diese Folge gab Gardner an.)

Euler gab mit f(n)=n²+n+41 im Jahr 1772 ein vielgerühmtes Polynom an, das eine stattliche Anzahl von Primzahlen erzeugt (es ist sogar bis heute der Rekordhalter).

Durch die Substitution n=k-40 erhält man f(k)=k²-79k+1601, womit man für k=0 bis k=79 80 Primzahlen in Folge erzeugt. Hier noch einige andere Primzahlpolynome:

Nun beweisen wir die oben angegebenen Eigenschaften:

1) f(xï y) ist prim  
Da x,yÎ N sind, ist BÎZ und damit B²Î N₀.
a ) B²>0 Þ ï B²-1ï =B²-1 Þ f(xï y)=2
b ) B²=0 Þ f(xï y)=[ï -1ï -(-1)]+2=× 2+2º y+1
außerdem gilt: B²=0 Þ B=0 Þ x(y+1)=y!+1, also y+1ï y!+1 und
damit ist y+1 prim nach dem Satz von Wilson!

2) jede Primzahl wird erzeugt
a ) f(1ï 1)=2, also wird 2 erzeugt
b ) Es sei p ungerade und prim. Dann gilt nach dem Satz von Wilson:
pï (p-1)!+1 und damit ist Î N. Es sei nun zusätzlich
y=p-1. Dann: x(y+1)=x× p=(p-1)!+1=y!+1 Þ B=0 Þ f(xï y)=y+1=p
Wir haben also ein Rezept, wie man die Argumente von f zu einem vorgegebenen p findet.

3) ungerade p werden nur einmal erzeugt
Es sei p ungerade prim. Da f(x,y)= ist p=y+1. Damit f den Wert y+1¹ 2 annimmt, muß B=0 sein, also auch x(y+1)=y!+1. Dann ist
x=. Nur diese Wahl für x und y führt auf den Funktionswert p.

AUFGABE 3.54  
a) Berechne die Argumente x und y, für die gilt f(xïy)=
        (1) 3 (2) 5 (3) 7 (4) 11 (5) 13
b) Wie viele Stellen hat x in: f(xï22)=23?

Download Kap_3_5 (26 KB)

Copyright © Michael Dorner, Januar 2002.