Hier ist ja wieder etwas los ... - Primzahltest

[neu...@tuhh.de]

Moin moin alle.
Schön das ein paar neue und auch alte Namen wieder da sind.
Das läßt mich auch - nach längerer, z.T. krankheitsbedingter Abwesenheit - in die Tasten greifen:

Ich fand im Spektrum der Wissenschaft einen Artikel unter
DIE FABELHAFTE WELT DER MATHEMATIK
Löst eine einfache Formel die vielen Rätsel um Primzahlen?
https://www.spektrum.de/kolumne/primzahlgeneratoren-loest-eine-formel-die-vielen-raetsel-um-primzahlen/2191965

Darin wird f(x)= [ cos²( Pi*( (x-1)! +1 )/x ) ] (wobei [.] abrundet).
Falls x eine Primzahl ist, ist das Ergebnis ein ganzzahliges Vielfaches von π, ansonsten nicht. f(x) =1 ==> x ist prim!

(Dass das für alle Werte von x gilt, hat Joseph Louis Lagrange im Jahr 1771 bewiesen, die Tatsache ist aber als »Satz von Wilson« bekannt. Der Mathematiker John Wilson hatte diesen Zusammenhang im 18. Jahrhundert als Vermutung zwar hervorgebracht – aber nicht als Erster. Tatsächlich hatte bereits der Gelehrte Alhazen um das Jahr 1000 eine entsprechende Vermutung formuliert, die jedoch in Vergessenheit geriet.)

Benutzt wird f(x) hier als Primzahltest für x.
Ich finde das ist mit Kanonen auf Spatzen schießen!
Untersucht man ((x-1)! +1 )/x, findet man als Phänomen, dass x Teiler dieses Ausdrucks ist, für alle Primzahlen x:
(1+1)/2=1, (1*2+1)/3=1, (1*2*3*4+1)/5=5, (6!+1)/7=103 … aber (1*2*3+1)/4=7/4, (5!+1)/6=121/6, …

Aber auch (x-1)! /x ist interessant. Hier findet man, dass x Teiler von (x-1)! für x nicht prim, d,h, (x-1)! Mod x= 0 (außer x=4):
Das müßte man beweisen:
5!/6=20, 9!/10=4480 … außer 3!/4=1,5!!! Das der Ausdruck für x Prim Teilerfremd ist ist klar,
aber warum man immer für alle Primfaktoren von x entsprechende Teiler in der Fakultät auffindbar sind erschließt sich nicht sofort.

Angenommen es sei so, dann folgt, dass (x-1)! mod x= 0 für alle x nicht prim (außer 4), also auch (x-1)! mod x^(x-1)= 0 für alle x nicht prim (außer 4).
Das läßt sich aber ohne große Zahlen (jedenfalls nicht großer n) für die Fakultäten iterieren: x= 1, x= x*i mod n (i=1…n-1)

Beispiele:
n=2 x=1, x=x*1 mod 2: 1
n=3 … : 1 2
n=4 … : 1 2 2
n=5 … : 1 2 1 4
n=6 … : 1 2 0 … 0
n=7 … : 1 2 6 3 1 6
n=8 … : 1 2 6 0 … 0
n=9 … : 1 2 6 6 3 0 … 0
…
Oder eben als kleines Python-Programm:
(Leerstellen (Blanks), hier „ _ “ Unterstriche!)

# Unterprogramm Primzahdetektor
def prim(n):
___if n==1: return
___if n==4: return False
___x=n-1; m=n;
___for n in range(m-2,1,-1):
______x=(x*n)%m
______if x==0:return False
___return True

Ich finde das ist ein "netter" Algorithmus.
Kennt den schon jemand? (Wo find ich es?)

Viel Spaß mit der "Materie" und einen schönen Sonntag.

VG Siggi N.

[neu...@tuhh.de]

Hi!
Ich mußte die Beweis-Idee des Satzes von Wilson erst erinnern, und trage ihn deshalb hier noch nach.
Er ist etwas tricky – man braucht die modulare Arithmetik:
Für x prim ist die Menge ZIx:= {0,1,2,…,x-1} mod x (d.h. das Rechnen mit Resten modulo x) ein Körper,
d.h. (+,ZIx) und (*,ZIx\0) (wobei x-1= -1 weil 1 + x-1 = 0) sind Gruppen.
Und, die Ordnung {1,2,…,x-1} ist gerade und 1 und -1 sind Idempotent d.h. 1²=(-1)²=1.
Daher gilt für jedes a aus {2,…,x-2} das Invers b, mit a*b=1, und b ungleich a, ist auch in {2,…,x-2}.
Damit folgt aber 1*2*…*(x-1)= -1 oder x teilt [1*2*…*(x-1) + 1] = 0.

Außerdem rechne ich ja nicht ((n-1)! +1) mod n sodern ... * k) mod n) *(k+1) mod n) * ...) * (n-1) mod n.
Wegen der Rechenregeln der Modulo-Arithmetik r mod n * s mod n = rs mod n, folgt dann aber auch:
[1 * 2 * … * (x-1)] mod n = 1 mod n * 2 mod n * … * (x-1) mod n, muß für n nicht prim genau dann ungleich -1= (n-1) sein.

Damit wäre am Ende der Iteration sicher zu ermitteln ob n prim ist. Ist n aber nicht prim, dann wäre ZIn kein Körper (Ring mit Nullteiler).
Das führt dazu, daß in der Abfolge ( …((1 mod n *)2 mod n *) … * k mod n= 0 auftritt, und die Null sich fortsetzt.
==> Wenn also eine Null auftritt, ist n sicher nicht prim.
QED

Das war vollständigkeitshalber noch nachzutragen. ;-)

Gruß Siggi N.