|
Plauderecke Alles, was garantiert nichts mit Physik zu tun hat. Seid nett zueinander! |
|
Themen-Optionen | Ansicht |
#1
|
|||||
|
|||||
Math Wilson Primgenerator
Ich moechte mich nochmals mit dem Algorithmus von Wilson beschaeftigen, der alle Primzahlen erzeugt.
http://www.quanten.de/forum/showthre...?t=1257&page=4 Ausserdem moechte ich mich von Emotionallogik und Internet Physikkriegen erholen. Bei Wilson geht es mir weniger um die Primzahlen sondern den frac Operator und die Fakultaet. Laesst sich hier eventuell eine Regel fuer den Frac Operator herleiten ? Dazu moechte ich meine schnelle Beweisfuehrung des notwendigen Teils von Wilsons Primzahlsatz nochmals darstellen. Meine Beweisfuehrung basiert auf Hilfssaetzen, die man aus folgendem wichtigen Satz herleiten kann : Fundamentalsatz 1) Zitat:
Gegeben seien die natuerlichen Zahlen a und b sowie deren Summe s=a+b Voraussetzung : ************** a und b sollen keinen gemeinsamen Primfaktor aufweisen Widerspruchs-Annahme : ******************* s habe einen gemeinsamen Primfaktor k mit a oder b Dann laesst sich s schreiben als s=k*S (wobei S=s/k und ganzzahlig ist) Sei a die Zahl mit dem Primfaktor k entsprechend a=k*A Dann laesst sich aber b=s-a schreiben als b=k*S-k*A=k*(S-A) Und damit enthielte auch b den Primfaktor k Das widerspricht aber der Voraussetzung. Daher kann c weder mit a noch b einen gemeinsamen Primfaktor aufweisen, wenn auch a und b keinen gemeinsamen Primfaktor aufweisen. Hilfsmittel Primorial (Primzahlfakultaet) : ***************************** Zitat:
Zitat:
Schneller Beweis (Schneller als Euklid) : Es existieren unendlich viele Primzahlen. ************************************************** ********* Man betrachte n#=2*3*5 ...*n sowie S=n#+1. S kann wegen Satz 1 keine Primfaktoren von n# aufweisen. Auch wenn S zusammengesetzt ist, so muss dessen kleinester Primfaktor daher groesser als n sein. Damit existiert zu jedem Primorial n# und damit zu jeder Primzahl n eine Primzahl n1 die groesser als n ist. => Es gibt unendlich viele Primzahlen. ************************* (Der Beweis wuerde auch mit der Fakultaet einer Primzahl funktionieren, siehe Satz 4) Euklids Beweis enthaelt einen Spezialfall von Satz 1, aber die getrennte Formulierung halte ich fuer anschaulicher. Kennt man Satz 1, gibt es keinen schnelleren Beweis. => Satz 2) Zitat:
Zitat:
Ge?ndert von richy (05.09.11 um 14:31 Uhr) |
#2
|
||||
|
||||
AW: Math Wilson Primgenerator
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:
Zitat:
Ge?ndert von richy (20.07.11 um 04:29 Uhr) |
#3
|
||||
|
||||
AW: Math Wilson Primgenerator
Herleitung Satz 4 :
************** Die Verwandtschaft von k# und k! ************************** k! kann in ein Primoral k# sowie einen Ausdruck m faktorisiert werden : k!=k#*m m stelllt dann das Produkt aller Nichtprimzahlen in n! dar. Beispiel : 8!=2*3*4*5*6*7*8 8!=2*3*5*7 * 4*6*8 8!=7#*4*6*8=7#*2*2*2*3*2*2*2 Fuer k! sei k eine Primzahl. Dann "zerfaellt" jede Nichtprimzahl in Primfaktoren kleiner k. k! kann somit von den enthaltenen Primfaktoren wie k# betrachtet werden. Fuer k! sei k keine Primzahl. Der groesste Primfaktor in k! sei p1. Koennen die Zahlen p1,p1+1,p2+2 .... n nun einen Primfaktor p2 enthalten der groesser ist als p1 ? Mit Sicherheit nicht, denn ansonsten waere dies der groesste Primfaktor in k!. => Satz 4) Zitat:
Ge?ndert von richy (20.07.11 um 18:09 Uhr) |
#4
|
||||
|
||||
AW: Math Wilson Primgenerator
Herleitung Satz 3 aus Satz 2)
Zitat:
Zunaechst moechte ich den einfachen Fall annehmen eines Primorials p#. Aus Satz 1) folgt, dass p#+1 keinen Primfaktor von p# enthalten kann. Dies gilt selbstverstaendlich auch wenn p#+1 keine Primzahl, also zusammengesetz ist. p#+1 ist somit eine Primzahl (die naechste Prizahl nach p) oder p#+1 ist eine zusammengesetzte Zahl Wenn nun p#+1 eine zusammengesetze Zahl ist, dann ist die kleinstmoegliche Zahl, die fuer p#+1 in Frage kommt gerade das Quadrat der auf p folgenden Primzahl ! Satz 3 : Zitat:
Ge?ndert von richy (20.07.11 um 18:05 Uhr) |
#5
|
|||||
|
|||||
AW: Math Wilson Primgenerator
Zwischen-Zusammenfassung :
Hilfsmittel Primorial (Primzahlfakultaet) : ***************************** Zitat:
Zitat:
Zitat:
Zitat:
Zitat:
Ge?ndert von richy (20.07.11 um 18:13 Uhr) |
#6
|
||||
|
||||
AW: Math Wilson Primgenerator
Zitat:
das finde ich gut so, dass du dich erholen möchtest. Bei deinen Math-Beiträgen lese ich gerne mit, obwohl ich leider sehr selten eigene Beiträge dazu beisteuern kann. M.f.G. Eugen Bauhof |
#7
|
|||||
|
|||||
AW: Math Wilson Primgenerator
Zitat:
Ok, ich probiers mal. Aussage A) Zitat:
(7-1)!=2*3*4*5*6=720 720+1=721=7*103 (tja wie ein Wunder gell :-) Das Wunder, dass p(k) enthalten sein muss und nicht alleine Primfaktorn groesser p(k) kann ich im Moment nicht zeigen. Wahrscheinlich ist dies recht aufwendig und gehoert zum hinreichenden Teil. EDIT Die Betrachtung von Aussage A fuer p=nichtprim wird im naechsten Beitrag zu einem eleganten Beweis fuehren. Dennoch hier nochmals meine Beweisidee von 2010 Fuer folgende Aussage Zitat:
Zitat:
Wenn (k-1)!+1 / k ohne Rest teilbar ist, dann ist k eine Primzahl. Teilbarkeit bedeutet, dass a) k ein Primfaktor von (k-1)!+1 ist, ODER b) k eine zusammengesetzte Zahl aus Primfaktor von (k-1)!+1 ist, was zu widerlegen ist. a) wurde schon ueber Aussage A behandelt. K sei nun eine zusammengesetzte Zahl. Im Moment muss ich vor mir selbst kapitulieren, denn ich komme einfach nicht darauf wie ich dies damals so schnell bewiesen hatte. Gluecklicherweise hatte ich dies aber etwas ausfuehrlicher kommentiert : Zitat:
(p-1)! +1 kann keinen Primteiler des Intervalls [2..(p-1)] aufweisen. Daraus folgt fuer die kleinste Zahl die (p-1)! +1 darstellen kann (p-1)! +1=p*p. Das ist die kleinste Zahl die p teilen muss. Und die kleinste zusamengesetzte Zahl die dazu in der Lage waere waere p=p*p Hilfe, mein Beweis scheint tatsaechlich zu stimmen. Allerdings gefaellt mir noch nicht, dass ich scheinbar voraussetze, dass p eine Primzahl ist. Ich sollte Aussage A noch fuer Nichtprimzahlen formulieren. Satz 2 habe ich bereits auf Fakultaeten verallgemeinert. Ebenso moechte ich dies noch bei Satz 3 versuchen. Dann waere alles komplett. Ge?ndert von richy (20.07.11 um 05:35 Uhr) |
#8
|
||||
|
||||
AW: Math Wilson Primgenerator
Nicht alle Saetze sind fuer den Beweis notwendig, aber ich moecht spaeter den Frac Operator genauer untersuchen und schaden koennen diese nicht.
Zuerst moechte ich Aussage A fuer k=nichtprim betrachten : Zitat:
Alle Primfaktoren von (k-1)!+1 sind groesser gleich p(n+1) Und da p(n+1)>k kann k keinen dieser Primfaktoren kuerzen. Ueber Aussage A im letzten Beitrag wurde gezeigt, dass eine Primzahl p ein Teiler sein kann. Aussage A) Zitat:
Etwas laenger aber eleganter und genauer als die vorherige Methode Allerdings koennte auch diese noch eine weitere Anwendung finden. Man weiss nie. Ge?ndert von richy (20.07.11 um 13:53 Uhr) |
#9
|
||||
|
||||
AW: Math Wilson Primgenerator
Sodele jetzt noch der Vollstaendigkeit wegen :
Satz 2: Zitat:
Zitat:
Fall 1 : In k ! sei k prim ****************** Aus Satz 2b) folgt unmittelbar p(n) sei die n-te Primzahl. Wenn p(n)!+1 eine Primzahl ist,dann gilt : p(n)!+1>=p(n+1) Wenn p(n)!+1 keine Primzahl ist,dann gilt : p(n)!+1>=p(n+1)^2 Fall 2 : In k ! sei k nichtprim ********************* p(n) sei die n-te Primzahl. k=p(n)+z, mit 0<z<p(n+1) aus Satz 4 folgt : Wenn k!+1 eine Primzahl ist,dann gilt : k!+1>=p(n+1) Wenn k!+1 keine Primzahl ist,dann gilt : k!+1>=p(n+1)^2 da p(n+1)>k gilt auch k!+1>k^2, falls k!+1 keine Primzahl ist Beispiel : 2!+1 ist kleiner 2^2 => 3 ist prim 3!+1 ist kleiner 3^2 => 7 ist prim 4!+1 ist kleiner 4^2 => 13 ist prim 5!+1 ist groesser 5^2 => keine Entscheidung fuer 121 Die Bedingung ist fuer k>4 auch nicht mehr interessant Fall1/2 lassen sich Zusammenfassen Satz 3b) Zitat:
Ge?ndert von richy (20.07.11 um 18:01 Uhr) |
#10
|
|||||||||||
|
|||||||||||
AW: Math Wilson Primgenerator
Groesse Zusammenfassung
******************** Hilfsmittel Primorial (Primzahlfakultaet) : ***************************** Zitat:
Zitat:
Zitat:
Zitat:
Zitat:
Zitat:
Zitat:
Zitat:
Zitat:
Aussage A1 : Zitat:
Aussage A2 (Widerpruchsbeweis) Zitat:
Alle Primfaktoren von (k-1)!+1 sind groesser gleich p(n+1) Da gilt p(n+1)>k, kann k keinen dieser Primfaktoren kuerzen. Damit ist Satz ii gezeigt. Ge?ndert von richy (20.07.11 um 19:09 Uhr) |
Lesezeichen |
|
|