Primzahlsatz von Wilson :
Satz A) Ist p eine Primzahl, dann ist [1+(p-1)!] / p eine ganze Zahl.
Satz B) Wenn (p-1)!+1 / p ohne Rest teilbar ist, dann ist p eine Primzahl
Satz A) zu beweisen ist recht aufwendig und fuer Primfakultaeten (Primorials) gilt er nicht. Er ist hinreichend.
Satz B) ist nicht hinreichend, denn es koennte sein, dass auch Nichtprimzahlen diesen Satz erfuellen. Er ist schwaecher als Satz A und laesst sich mir den Saetzen 1-4 beweisen :
Widerspruchsbeweis von Satz B
( EDIT : Im Beitrag #8 hab ich einen noch eleganteren Beweis angegeben)
Zitat:
Alle Primteiler von (p-1)! +1 sind groesser als (p-1)
Wenn (p-1)! +1 ohne Rest durch p teilbar ist, dann enthaelt (p-1)! +1 den kleinsten moeglichen Primteiler p
Waere der Teiler zusammengesetzt so muesste dieser Teiler groesser p^2 sein.
Dann muesste aber gelten p>=p^2 und das ist nur fuer p=+-1 kein Widerspruch.
Daher kann p keine zusammengesetzte Zahl sein.
|
Der kurzeste Primzahlgenerator der Welt basiert auf Satz A) und erzeugt damit algorithmisch tatsaechlich alle existierenden Primzahlen (Mit Einschraenkungen bezueglich dem praktischem Einsatz wegen der Fakultaet ):
Zitat:
|
Zitat von richy
> for p from 1 to 1000 do
> if frac(((1+(p-1)!)/p))=0 then printf(`%g `,p);fi;od
|