Quanten.de Diskussionsforum  

Zur?ck   Quanten.de Diskussionsforum > Plauderecke

Hinweise

Plauderecke Alles, was garantiert nichts mit Physik zu tun hat. Seid nett zueinander!

Antwort
 
Themen-Optionen Ansicht
  #1  
Alt 18.07.11, 21:26
Benutzerbild von richy
richy richy ist offline
Singularität
 
Registriert seit: 01.05.2007
Ort: karlsruhe
Beitr?ge: 4.170
Standard 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:
Besitzen zwei natuerliche Zahlen a und b keine gemeinsamen Primfaktoren, so besitzt auch die Summe dieser Zahlen:
s = a + b weder mit a und b einen gemeinsamen Primfaktor !
Widerspruchsbeweis :
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:
Für eine natürliche Zahl n ist das Primorial n# definiert als das Produkt aller Primzahlen kleiner gleich n.
http://de.wikipedia.org/wiki/Primorial
Beispiel : 5#=2*3*5
Satz 4) Herleitung in gesondertem Beitrag
Zitat:
Jede Fakultaet k! laesst sich in einen Faktor m sowie ein Primorial p# aufspalten : k! =p#*m, wobei p der groesste Primfaktor von k! darstellt und m das Produkt der Nichtprimfaktoren.
m enthaelt dann in allen Faellen keine Primfaktoren die groesser als p sind.
Der Beweis zu Wilsons Primzahlsatz benoetigt spezielle Anwendung von Satz 1) auf Primorials und Fakultaeten. Ich moechte eine wichtige Anwendung Satz 2) an einem Beipiel herleiten :

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:
Bildet man ein Primorial p#, so folgt aus Satz 1), dass der kleinste Primfaktor von p#+1 groesser als p sein muss.
Mit Satz 4)
Bildet man eine Fakultaet k!, so folgt aus Satz 1), dass der kleinste Primfaktor von k!+1 groesser als der groesste Primfaktor von k! sein muss.
Satz 3) Herleitung in gesondertem Beitrag

Zitat:
p(n) sei die n te Primzahl
Wenn p(n)#+1 eine zusammengesetze Zahl ist, dann ist die kleinstmoegliche Zahl, die fuer p(n)#+1 in Frage kommt das Quadrat der auf p(n) folgenden Primzahl also p(n+1)^2

p(n)#+1>=p(n+1)^2 (nichtprim)
p(n)#+1>=p(n+1) (prim)

Ge?ndert von richy (05.09.11 um 15:31 Uhr)
Mit Zitat antworten
  #2  
Alt 18.07.11, 21:30
Benutzerbild von richy
richy richy ist offline
Singularität
 
Registriert seit: 01.05.2007
Ort: karlsruhe
Beitr?ge: 4.170
Standard 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:
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

Ge?ndert von richy (20.07.11 um 05:29 Uhr)
Mit Zitat antworten
  #3  
Alt 18.07.11, 22:19
Benutzerbild von richy
richy richy ist offline
Singularität
 
Registriert seit: 01.05.2007
Ort: karlsruhe
Beitr?ge: 4.170
Standard 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:
Jede Fakultaet k! laesst sich in einen Faktor m sowie ein Primorial p# aufspalten : k! =p#*m, wobei p der groesste Primfaktor von k! darstellt und m das Produkt der Nichtprimfaktoren.
m enthaelt dann in allen Faellen keine Primfaktoren die groesser als p sind.

Ge?ndert von richy (20.07.11 um 19:09 Uhr)
Mit Zitat antworten
  #4  
Alt 18.07.11, 23:16
Benutzerbild von richy
richy richy ist offline
Singularität
 
Registriert seit: 01.05.2007
Ort: karlsruhe
Beitr?ge: 4.170
Standard AW: Math Wilson Primgenerator

Herleitung Satz 3 aus Satz 2)
Zitat:
Bildet man ein Primorial p#, so folgt aus Satz 1), dass der kleinste Primfaktor von p#+1 groesser als p sein muss.
Daraus folgt eine quadratische Schranke :
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:
p(n) sei die n te Primzahl
Wenn p(n)#+1 eine zusammengesetze Zahl ist, dann ist die kleinstmoegliche Zahl, die fuer p(n)#+1 in Frage kommt das Quadrat der auf p(n) folgenden Primzahl also p(n+1)^2

p(n)#+1>=p(n+1)^2 (nichtprim)
p(n)#+1>=p(n+1) (prim)

Ge?ndert von richy (20.07.11 um 19:05 Uhr)
Mit Zitat antworten
  #5  
Alt 19.07.11, 00:53
Benutzerbild von richy
richy richy ist offline
Singularität
 
Registriert seit: 01.05.2007
Ort: karlsruhe
Beitr?ge: 4.170
Standard AW: Math Wilson Primgenerator

Zwischen-Zusammenfassung :

Hilfsmittel Primorial (Primzahlfakultaet) :
*****************************
Zitat:
Für eine natürliche Zahl n ist das Primorial n# definiert als das Produkt aller Primzahlen kleiner gleich n.
http://de.wikipedia.org/wiki/Primorial
Beispiel : 5#=2*3*5
Hauptsatz 1)
Zitat:
Besitzen zwei natuerliche Zahlen a und b keine gemeinsamen Primfaktoren, so besitzt auch die Summe dieser Zahlen:
s = a + b weder mit a und b einen gemeinsamen Primfaktor !
Satz 4)
Zitat:
Jede Fakultaet k! laesst sich in einen Faktor m sowie ein Primorial p# aufspalten : k! =p#*m, wobei p der groesste Primfaktor von k! darstellt und m das Produkt der Nichtprimfaktoren.
m enthaelt dann in allen Faellen keine Primfaktoren die groesser als p sind.
Satz 2)
Zitat:
Bildet man ein Primorial p#, so folgt aus Satz 1), dass der kleinste Primfaktor von p#+1 groesser als p sein muss.
Mit Satz 4)
Bildet man eine Fakultaet k!, so folgt aus Satz 1), dass der kleinste Primfaktor von k!+1 groesser als der groesste Primfaktor von k! sein muss.
Satz 3)
Zitat:
p(n) sei die n te Primzahl
Wenn p(n)#+1 eine zusammengesetze Zahl ist, dann ist die kleinstmoegliche Zahl, die fuer p(n)#+1 in Frage kommt das Quadrat der auf p(n) folgenden Primzahl also p(n+1)^2

p(n)#+1>=p(n+1)^2 (nichtprim)
p(n)#+1>=p(n+1) (prim)

Ge?ndert von richy (20.07.11 um 19:13 Uhr)
Mit Zitat antworten
  #6  
Alt 19.07.11, 10:12
Benutzerbild von Bauhof
Bauhof Bauhof ist offline
Singularität
 
Registriert seit: 07.12.2008
Ort: Nürnberg
Beitr?ge: 2.105
Standard AW: Math Wilson Primgenerator

Zitat:
Zitat von richy Beitrag anzeigen
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 Internetz Physikkriegen erholen.
Hallo Richy,

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
Mit Zitat antworten
  #7  
Alt 20.07.11, 02:28
Benutzerbild von richy
richy richy ist offline
Singularität
 
Registriert seit: 01.05.2007
Ort: karlsruhe
Beitr?ge: 4.170
Standard AW: Math Wilson Primgenerator

Zitat:
Zitat von BauhoF
obwohl ich leider sehr selten eigene Beiträge dazu beisteuern kann.
Schade denn ich habe im Moment selber etwas Muehe meinen Beweis nachzuvollziehen.
Ok, ich probiers mal.
Aussage A)
Zitat:
p(n) sei die n-te Primzahl.
p(n)-1 muss keine Prinzahl sein und ist kleiner als p(n)
In (p(n)-1)! ist daher der Primfaktor p(n) nicht enthalten sondern der groesste Primfaktor von (p(n)-1)! ist p(n-1), auch wenn p(n)-1 keine Primzahl ist. (p(n)-1)!=p(n-1)#*m

(Satz 4 : Auch in m kann p(n) nicht enthalten sein, denn dann waere die zusammengesetzte Zahl groesser p(n-1))

Wegen Satz 2) sind alle Primfaktoren von (p(n)-1)!+1 groesser gleich p(n)
Beispiel :
(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 von Wilson
Wenn (p-1)! +1 ohne Rest durch p teilbar ist, dann enthaelt (p-1)! +1 den kleinsten moeglichen Primteiler p
hatte ich einen Widerspruchsbeweis angegeben, an dem ich gerade etwas haenge :
Zitat:
Zitat von richy 2010
Waere der Teiler zusammengesetzt so muesste dieser Teiler groesser p^2 sein.
Behauptung :
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:
Zitat von richy 2010
Wegen Satz 2)
(p-1)! +1 kann keinen Primteiler des Intervalls [2..(p-1)] aufweisen.
Alle Primteiler von (p-1)! +1 sind somit groesser als (p-1)

Der kleinste dieser Primteiler ist p (Falls p ein Teiler ist)
Der kleinste zusammengesetze Teiler ist p^2

Nochmal in einfachen Worten

Man stelle sich die Primfaktorzerlegung von (p-1)! + 1 vor.
Alle Primfaktoren muessen groesser als (p-1) sein. Dass (p-1)! + 1 durch p teilbar ist, kann gerade noch erfuellt werden. (Vorausgesetzt p ist als Primfaktor enthalten.)
Denn p>p-1
Waere p aber keine Primzahl, so waere es das Produkt mindestens zweier der Primfaktoren von (p-1)! + 1.
Das kleinste Uebel waere p^2. Aber selbst dies ist zu gross.
Also kann p hoechstens ein Primfaktor von (p-1)! + 1 sein und nicht ein Produkt mehrerer seiner Primfaktoren.
Zwei Zahlen. Beide groesser gleich p. Deren Produkt soll gleich p sein. Des geht net :-) (Ausser fuer eins)
Aaarrg ist das tatsaechlich so einfach ?
(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 06:35 Uhr)
Mit Zitat antworten
  #8  
Alt 20.07.11, 05:17
Benutzerbild von richy
richy richy ist offline
Singularität
 
Registriert seit: 01.05.2007
Ort: karlsruhe
Beitr?ge: 4.170
Standard 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:
p(n) sei die n-te Primzahl.
k sei eine zusammengesetzte Zahl k=p(n)+z < p(n+1)

Fall 1: z=1, k=p(n)+1 < p(n+1)
k-1 ist die Primzahl p(n) und kleiner als k
Der groesste Primfaktor von (k-1)! ist p(n)
Wegen Satz 2) sind alle Primfaktoren von (k-1)!+1 groesser gleich p(n+1)
da p(n+1)>k
Wegen Satz 2) sind alle Primfaktoren von (k-1)!+1 groesser k

Fall 2: z<>1 k=p(n)+z < p(n+1)
k-1 ist die zusammengesetzte Zahl p(n)+(z-1) und kleiner als k
Der groesste Primfaktor von (k-1)! ist p(n) (Satz 4)
Wegen Satz 2) sind alle Primfaktoren von (k-1)!+1 groesser gleich p(n+1)
da p(n+1)>k
Wegen Satz 2) sind alle Primfaktoren von (k-1)!+1 groesser k
Beide Faelle fuehren somit zum selben Resultat, insbesonders zu :
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:
p(n) sei die n-te Primzahl.
p(n)-1 muss keine Prinzahl sein und ist kleiner als p(n)
In (p(n)-1)! ist daher der Primfaktor p(n) nicht enthalten sondern der groesste Primfaktor von (p(n)-1)! ist p(n-1), auch wenn p(n)-1 keine Primzahl ist.
Wegen Satz 2) sind alle Primfaktoren von (p(n)-1)!+1 groesser gleich p(n)
Und damit ist Wilsons Primsatz 2) (notwendiger nicht hinreichender Teil) verifiziert

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 14:53 Uhr)
Mit Zitat antworten
  #9  
Alt 20.07.11, 18:57
Benutzerbild von richy
richy richy ist offline
Singularität
 
Registriert seit: 01.05.2007
Ort: karlsruhe
Beitr?ge: 4.170
Standard AW: Math Wilson Primgenerator

Sodele jetzt noch der Vollstaendigkeit wegen :

Satz 2:
Zitat:
a) Bildet man ein Primorial p#, so folgt aus Satz 1), dass der kleinste Primfaktor von p#+1 groesser als p sein muss.
Mit Satz 4)
b) Bildet man eine Fakultaet k!, so folgt aus Satz 1), dass der kleinste Primfaktor von k!+1 groesser als der groesste Primfaktor von k! sein muss.
Satz 3
Zitat:
p(n) sei die n-te Primzahl
Wenn p(n)#+1 eine zusammengesetze Zahl ist, dann ist die kleinstmoegliche Zahl, die fuer p(n)#+1 in Frage kommt das Quadrat der auf p(n) folgenden Primzahl also p(n+1)^2

p(n)#+1>=p(n+1)^2 (nichtprim)
p(n)#+1>=p(n+1) (prim)
Weche Schranken in Satz 3 ergeben sich wenn ich wie in Satz 2b) die Fakulatet statt der Primzahlfakultaet betrachte ?

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:
p(n) sei die n-te Primzahl und groesster Primfaktor von k !
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 (und immer fuer k>4)

Ge?ndert von richy (20.07.11 um 19:01 Uhr)
Mit Zitat antworten
  #10  
Alt 20.07.11, 19:37
Benutzerbild von richy
richy richy ist offline
Singularität
 
Registriert seit: 01.05.2007
Ort: karlsruhe
Beitr?ge: 4.170
Standard AW: Math Wilson Primgenerator

Groesse Zusammenfassung
********************

Hilfsmittel Primorial (Primzahlfakultaet) :
*****************************
Zitat:
Für eine natürliche Zahl n ist das Primorial n# definiert als das Produkt aller Primzahlen kleiner gleich n.
http://de.wikipedia.org/wiki/Primorial
Beispiel : 5#=2*3*5
Hauptsatz 1)
Zitat:
Besitzen zwei natuerliche Zahlen a und b keine gemeinsamen Primfaktoren, so besitzt auch die Summe dieser Zahlen:
s = a + b weder mit a und b einen gemeinsamen Primfaktor !
Satz 4)
Zitat:
Jede Fakultaet k! laesst sich in einen Faktor m sowie ein Primorial p# aufspalten : k! =p#*m, wobei p der groesste Primfaktor von k! darstellt und m das Produkt der Nichtprimfaktoren.
m enthaelt dann in allen Faellen keine Primfaktoren die groesser als p sind.
Satz 2 a)
Zitat:
Bildet man ein Primorial p#, so ist der kleinste Primfaktor von p#+1 groesser als p
Satz 2 b)
Zitat:
Bildet man eine Fakultaet k!, so ist der kleinste Primfaktor von k!+1 groesser als der groesste Primfaktor von k!
Satz 3a)
Zitat:
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
Satz 3b)
Zitat:
p(n) sei die n-te Primzahl und groesster Primfaktor von k !
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 (und immer fuer k>4)
Primzahlsatz von Wilson :
Zitat:
Satz i) Ist p eine Primzahl, dann ist [1+(p-1)!] / p eine ganze Zahl.
Satz ii) Wenn (p-1)!+1 / p ohne Rest teilbar ist, dann ist p keine zusammengesetzte Zahl
Programmcode :
Zitat:
> for p from 1 to 1000 do
> if frac(((1+(p-1)!)/p))=0 then printf(`%g `,p);fi;od
Verifikation :
Aussage A1 :
Zitat:
p(n) sei die n-te Primzahl.
p(n)-1 muss keine Prinzahl sein und ist kleiner als p(n)
In (p(n)-1)! ist daher der Primfaktor p(n) nicht enthalten sondern der groesste Primfaktor von (p(n)-1)! ist p(n-1), auch wenn p(n)-1 keine Primzahl ist. (p(n)-1)!=p(n-1)#*m

(Satz 4 : Auch in m kann p(n) nicht enthalten sein, denn dann waere die zusammengesetzte Zahl groesser p(n-1))

Wegen Satz 2) sind alle Primfaktoren von (p(n)-1)!+1 groesser gleich p(n)
=> Fuer eine Primzahl kann Satz ii erfuellt werden

Aussage A2 (Widerpruchsbeweis)
Zitat:
p(n) sei die n-te Primzahl.

k=p(n)+z, mit 0<z< p(n+1)
k-1 ist die Zahl p(n)+(z-1) und kleiner als k
k-1 kann sowohl prim als auch nichtprim sein.
Der groesste Primfaktor von (k-1)! in beiden Faellen ist p(n) (Satz 4)
Wegen Satz 2b) sind alle Primfaktoren von (k-1)!+1 groesser gleich p(n+1)
da p(n+1)>k
Wegen Satz 2b) sind alle Primfaktoren von (k-1)!+1 groesser k
=>
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 20:09 Uhr)
Mit Zitat antworten
Antwort

Lesezeichen

Themen-Optionen
Ansicht

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beitr?ge zu antworten.
Es ist Ihnen nicht erlaubt, Anh?nge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beitr?ge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.

Gehe zu


Alle Zeitangaben in WEZ +1. Es ist jetzt 17:14 Uhr.


Powered by vBulletin® Version 3.8.8 (Deutsch)
Copyright ©2000 - 2024, vBulletin Solutions, Inc.
ScienceUp - Dr. Günter Sturm