Euklids Primzahlbeweis |
| 18.03.2004, 22:12 | Toxman | Auf diesen Beitrag antworten » | ||
| Euklids Primzahlbeweis Seine Argumentation: Nimm dir die größte Primzahl: z.b: 13 (=P) (ist zwar nicht spektakulär, passt aber gut) -Multipiziere alle Primzahlen >= P N=2*3*5*7*11*13 (30030) - Schau dir die nächste Zahl an. (N+1=M) Jetzt kommt der Gag und mein Problem: Fall 1) M ist prim; toll, ich bin fertig Fall 2) M nicht prim. weniger gut, aber auch kein Problem, denn 'Alle Zahlen ( element N) sind prim oder aus Primzahlen zusammengesetzt' (Satz a) Jetzt ist Euklids Argumentation, dass wenigstens eine der Primzahlen, aus denen M zusammengesetzt ist, größer als P sein muss. (Satz b) Mein Problem ist, die beiden Sätze (a&b) zu beweisen. Wer hat da eine Idee für mich? THX by TOX |
||||
| 19.03.2004, 01:00 | Drödel | Auf diesen Beitrag antworten » | ||
| RE: Euklids Primzahlbeweis Also der Beweis zu a) sollte folgendermaßen gehen: Wenn eine Zahl n nicht prim ist, dann besitzt sie sogenannte nichttriviale Teiler. Nichttrivial ist der Teiler einer Zahl, wenn es die Zahl selbst oder 1 ist. Das heißt aber auch, dass die Zahl als Produkt mindestens zweier Zahlen n1 und n2 darstellbar ist. Sind n1 und n2 prim, dann sind wir damit fertig. Falls dies nicht der Fall ist, dann hat n1 und/oder n2 nichttriviale Teiler und kann weiter zerlegt werden..... bis am Ende eben nur noch Primteiler übrig sind... Nun zu Teil b): Wenn ich dich richtig verstehe, dann lautet die Behauptung: Sei N das Produkt aus allen Primzahlen bis zur Primzahl p. Dann hat N+1 einen Primteiler, der größer ist als P ... RIchtig ? Denk ... denk |
||||
| 19.03.2004, 07:47 | Toxman | Auf diesen Beitrag antworten » | ||
So was mit einem 'rekursiven' Beweis ist mir auch noch eingefallen. [QUOTE="Drödel"]Sei N das Produkt aus allen Primzahlen bis zur Primzahl p. Dann hat N+1 einen Primteiler, der größer ist als P ...[/QUOTE] Stimmt und das will ich noch beweisen. Schon mal danke Tox |
||||
| 19.03.2004, 09:29 | Drödel | Auf diesen Beitrag antworten » | ||
Nun, ich kann mich ja auch täuschen (hab mir das nur schnell mal eben im Kopf durchgedacht und keine Beweis dafür auf Papier probiert), aber ist dieses (Produkt aus allen Primzahlen bis zur Primzahl p) +1 nicht selber ne Primzahl? Dann hat es wohl auch einen Primteiler, der größer ist als p, oder? Ich vermute, das würde sich (falls es stimmt) durch vollständige Induktion beweisen lassen. Werd mal drüber nachdenken, aber vielleicht hilft das ja schon. Happy Mathing |
||||
| 19.03.2004, 10:19 | Ben Sisko | Auf diesen Beitrag antworten » | ||
Ich glaube auch, dass N+1 prim ist, aber das benötigt man hier gar nicht. Sei das Produkt aller Primzahlen (diese seien der Grösse nach geordnet, also . Seien nun die Primfaktoren von N+1(ebenfalls der Grösse nach geordnet), also . Wäre nun , so wäre , da ja . Dies ist ein Widerspruch. Ich denke so sollte ein formaler Beweis aussehen, auch wenn es intuitiv ja schon klar ist. Gruß vom Ben |
||||
| 19.03.2004, 21:08 | Polarfuchs | Auf diesen Beitrag antworten » | ||
Hallo Toxman, Beweis von Satz a) durch vollständige Induktion: 1.Induktionsanfang: Jede Primzahl besitzt eine Primfaktorzerlegung mit EINEM Faktor,dies gilt also für die Zahl 2. 2.Induktionssannahme: Jedes mit besitzt eine Primfaktorzerlegung. 3.Induktionsbehauptung: Dies gilt auch für n+1. 4.Beweis: Die Induktionsbehauptung ist wahr,wenn n+1 eine Primzahl ist. Ist dies nicht der Fall,dann ist n+1 von der Form Es ist p eine Primzahl,außerdem gilt . Laut Induktionsannahme besitzt A eine Primfaktorzerlegung,also Daraus folgt Die Eindeutigkeit der Primfaktorzerlegung braucht hier aus meiner Sicht nicht bewiesen zu werden. Polarfuchs |
||||
| Anzeige | ||||
|
|
||||
| 19.03.2004, 21:36 | Poff | Auf diesen Beitrag antworten » | ||
Ich denke soo einfach ist es nicht, denn es könnten immerhin ja auch verschiedene Potenzen bzw unterschiedliche Kombinationen von Potenzen der einzelnen Primzahlen in der Zerlegung auftauchen ... ... und ich kann leider noch nicht erkennen wie der Beweis von Polarfuchs dies umschifft :-/ .. wahrscheinlich steht nur wer auf meiner Leitung *g* 
. |
||||
| 19.03.2004, 22:55 | Toxman | Auf diesen Beitrag antworten » | ||
Schon mal Danke für die Antworten, nur leider kann ich mit Ben's Beweis noch nicht viel anfangen. Ich bin in der 12 und hab leider nur eine Art Grundkurs (wohne in Ba-Wü und kann hier keinen LK mehr wählen :P). Ich muss mir ihn nochmal anschauen, wahrscheinlich bekomm ich dass aber noch hin. THX by TOX |
||||
| 20.03.2004, 08:47 | Polarfuchs | Auf diesen Beitrag antworten » | ||
@Poff Ich weiß nicht,ob ich dein Problem richtig verstehe... Ich fange bei dem Beweis an: n+1 sei keine Primzahl. Ich wähle ein Beispiel: n+1=360=2^3*3^2*5 Ich schreibe es in der Form n+1=p*A mit p=2 und A=2^2*3^2*5: n+1=2*2^2*3^2*5 oder n+1=2*2*2*3*3*5 Es gilt A=p1*p2*...*pr, also A=2*2*3*3*5 Hier ist p1=p2 und p3=p4. Allerdings ist die Reihenfolge beliebig. Polarfuchs |
||||
| 20.03.2004, 14:41 | Toxman | Auf diesen Beitrag antworten » | ||
@ Polarfuchs: Bei deinem Beweis benutzt du für n+1 360. Da n aber das Produkt aus Primzahlen (einschließlich der 2 (!)) ist, ist n immer gerade, und damit kann n+1 nie gerade sein. Ich glaube (!) dass n+1 immer prim ist: Ein möglicher Teiler ist nach dem oben schon genannten Beweis das Produkt aus Primzahlen, die kleiner n sind. Da aber alle Primzahlen<n Teiler von n sind, können sie nicht gleichzeitig n+1 Teilen, da sie >1 sind. Also hat n+1 keine Teiler (>1) und ist somit immer prim. Wer was gegen den Beweis hat, büdde melden. Tox |
||||
| 20.03.2004, 17:56 | SirJective | Auf diesen Beitrag antworten » | ||
Toxman: Ich hab was gegen den Beweis, und zwar was wirksames... Ein Gegenbeispiel: 2*3*5*7*11*13+1 = 30031 = 59*509. Dein Beweis hakt an der Stelle "Da aber alle Primzahlen<n Teiler von n sind, können sie nicht gleichzeitig n+1 Teilen, da sie >1 sind." Selbst für 2*3*5 = 30 sind nicht alle Primzahlen < 30 Teiler der 30 - schon die 7 ist keiner. Wenn man aber bewiesen hat, dass jede natürliche Zahl > 1 durch mindestens eine Primzahl teilbar ist, dann weiß man, dass a=p1*...*pn + 1 durch mindestens eine Primzahl q teilbar ist (die vielleicht a ist), und dass q keine der p1, ..., pn sein kann (sonst würde sie sowohl a als auch a-1 teilen). Damit ist q eine weitere Primzahl. Übrigens funktioniert der Beweis auch dann, wenn man eine beliebige endliche Menge von Primzahlen nimmt, das müssen nicht die ersten n Stück sein. (In diesem allgemeineren Fall kann q auch kleiner sein als die verwendeten Primzahlen.) Gruss, SirJective |
||||
| 20.03.2004, 18:10 | Toxman | Auf diesen Beitrag antworten » | ||
Da hab ich gedacht ich hätte was gefunden und du machst mir wieder alles kaputt. Du bist gemein :rolleyes:Ich weiss irgendwie nicht, wie ich so überzeugt davon gewesen sein kann, da es meinem ersten Post wiederspricht. (sonst hätte ich nie einen Fall b)) Jetzt muss ich mir doch noch mal Ben's Beweis reinziehen. THXbyTOX |
||||
| 20.03.2004, 18:26 | Polarfuchs | Auf diesen Beitrag antworten » | ||
@Toxman Mein letzter Beitrag ist kein Beweis,ich wollte damit nur die Idee näher erläutern. n+1 steht (wie n) für eine beliebige natürliche Zahl,nicht zwangsläufig für für eine Primzahl.Ist es eine Primzahl,hat die Primfaktorzerlegung ohnehin nur EINEN Faktor. Ist es keine,siehe dir meinen Beweis nochmal an.Wenn ich den Beweis auch selbst formuliert habe,so habe ich das Prinzip auch erlernt und nicht erfunden.Eigentlich ist es ein Standardbeweis (wie z.B.,daß wurzel(2) irrational ist). Ich garantiere somit für die Richtigkeit. Es galt zu beweisen,daß jede natürliche Zahl eine Primfaktorzerlegung hat.Dies habe ich getan. Ohne dich unterschätzen zu wollen: Will man einen korrekten,noch nicht existierenden Beweis auf die Beine stellen,so sollte man schon mehr als oberflächliche Kenntnisse in der Zahlentheorie haben. (Was ich von mir mit Sicherheit (noch) nicht behaupten würde!) Dennoch wünsche ich dir viel Erfolg! :] Polarfuchs |
||||
| 20.03.2004, 20:42 | Toxman | Auf diesen Beitrag antworten » | ||
Ich würd mal sagen 2: 1 und die Zahl, oder hab ich dich da falsch verstanden? zu meiner Idee oben: ich glaub ich hab in der Mitte p(die ausgangsprimzahl) mit n (dem Produkt) verwechelst 
reichlich peinlich@ Polarfuchs: Ich glaube nicht, dass es noch viele, nicht schon bekannte Beweise für diese Frage gibt, die man ohne eine mathestudium verstehen kann. : ) Ich bin nur auf der Suche nach einem (mir) verständlichen Beweis, den ich selbst führen kann. Danke noch mal an alle für die Hilfe Tox |
||||
| 20.03.2004, 20:59 | Polarfuchs | Auf diesen Beitrag antworten » | ||
@Toxman Die Zahl 1 ist nicht als Primzahl definiert! Bei der Primfaktorzerlegung zerlegt man eine natürliche Zahl in möglichst kleine Faktoren. Allerdings müssen diese von 1 verscheiden sein. Ein Beweis durch vollständige Induktion setzt doch relativ geringe mathematische Vorkenntnisse voraus.Ich bezweifle,daß du einen einfacheren findest. Anmerkung: Ich habe mit Blick auf die links am Rande stehende Primzahl 17 bewußt diesen Beweis gewählt! 
Polarfuchs |
||||
| 03.11.2004, 10:36 | Braini | Auf diesen Beitrag antworten » | ||
Ich verstehe nicht ganz, wo dein Problem ist. Es gilt doch zu beweisen, dass es eine Primzahl größer 13 gibt. Als Vorraussetzung für diesen Beweis nutzt man den Fundamentalsatz der elementaren Mathematik, dass jede nat. Zahl N > 1 entweder eine Primzahl ist, oder aber sich eindeutig in ein Produkt endlich vieler, nicht notwendig verschiedener, Primzahlen p_1, p_2, ..., p_k zerlegen lässt. (1) Man beweist indirekt: Annahme: p ist die größte Primzahl Man multipliziert alle Primzahlen <= p und erhält nun die Zahl N Ist nun 1. N+1 eine Primzahl, dann ist das ein Widerspruch zur Annahme, das p die größte Primzahl ist 2. ist N+1 keine Primzahl, so muss es wegen (1) eine Primfatorzerlegung von N+1 geben. Da in der Faktorisierung von N alle Primzahlen <=p enthalten sind, ist es offentsichtlich nicht möglich mit denselben Primzahlen auch N+1 zu zerlegen, d.h. es muss eine weitere Primzahl q > p. -> Widerspruch zu Annahme! |
||||
| 03.11.2004, 12:40 | eule | Auf diesen Beitrag antworten » | ||
Um was geht es? Möchtest du den Beweis von Euklid ganz formal haben (Existenz u. Eindeuigkeit der Primfaktorenzerlegung usw.) oder reicht es zu zeigen dass es unendlich viele Primzahlen gibt. Für zweiteres hätte ich noch ein paar Alternativbeweise. |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |
|