 |
 |
 |
 |
 |
 |
Startseite » Forum » Sieb des Eratosthenes, Wurzel(n)
Sieb des Eratosthenes, Wurzel(n)
Universität / Fachhochschule
Tags: komplementärteiler, Primzahl, Primzahltests, Teil
 
|
  |
|---|
|
Hallo, beim Sieb des Eratosthenes streiche ich ja immer die Vielfachen einer Primzahl . Hierbei muss ich ja nur Vielfache von betrachten, wenn ich Primzahlen bis herausfinden will. Warum ist das so? Ein erster Beweisversuch... Ich komm aber irgendwie nicht weiter... Ich muss ja nur Vielfache von streichen, die sind, . es gilt: Das kann ich ja umstellen: Jetzt kann ich ja annehmen, dass ist.... Hilft mir das irgendwie weiter um zu zeigen das sein muss? Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
| Hierzu passend bei OnlineMathe: Online-Übungen (Übungsaufgaben) bei unterricht.de: |
|
 |
|
Wenn ich mich recht erinnere hast du letztens erst bewiesen, dass bei mindestens einer der beiden Teiler kleiner oder gleich sein muss - wende das doch einfach hier an. |
 |
|
Genau, für den Fall hatte ich das gezeigt. Jetzt geht es ja aber um den Fall bzw. Deshalb stehe ich etwas auf dem Schlauch... Ob EINE Zahl im Bereich von 2 bis prim ist lässt sich ja leicht zeigen: Wenn KEINE Primzahl ist, kann ich ja darstellen als wobei ja mindestens ein Faktor immer ist (das hatte ich ja schonmal gezeig). Wenn ich also keinen solchen Faktor von 2 bis finde, dann ist prim. Aber wie ich jetzt zeigen kann das sozusagen die anderen Zahlen schon gestrichen sind beim Sieb des Eratosthenes wenn ich alle Zahlen bis betrachtet habe ist halt irgendwie noch unklar... Desweiteren muss ich ja um zu prüfen, ob eine Zahl eine Primzahl ist nur kleinere Primzahlen als Teiler testen und keine anderen Zahlen. Wieso das so ist, ist mir ebenfalls nicht klar. |
|
|
|
> für den Fall hatte ich das gezeigt. Jetzt geht es ja aber um den Fall . Ich weiß nicht, wo du da ein zusätzliches Problem siehst: Wenn du eine Nichtprimzahl mit hast, d.h. auch einer Zerlegung mit und , dann weißt du doch aus deinen bisherigen Überlegungen, dass mindestens einer der Faktoren ist, was wegen dann natürlich auch nach sich zieht. |
|
|
|
Hmm, ok. Ich glaube das habe ich verstanden. Und wieso muss ich, um zu prüfen, ob eine Zahl eine Primzahl ist eigentlich nur kleinere Primzahlen als Teiler testen und keine anderen Zahlen? . wenn ich prüfen möchte ob die Zahl eine Primzahl ist, dann kann ich ja... der Reihe nach alle möglichen Teiler ( )testen (wenn ich keinen Teiler finde, dann Primzahl) nur kleinere Primzahlen testen, keine anderen Zahlen. Warum gilt b? |
|
|
|
Man kommt sich vor wie Sisyphos: Immer wenn man den Stein hochgewuchtet hat kommt eine Anfrage von dir, die zeigt, dass der Stein schon wieder heruntergerollt ist. Du (be)drängst einen mit deinen Anfragen in eine immer verschrobenere, verhedderte Richtung - warum so furchtbar kompliziert? Betrachte doch die Primfaktorzerlegung von und da den KLEINSTEN Primfaktor . Annahme: ist keine Primzahl. (*) Dann muss sein und außerdem gilt für den Komplementärteiler auf jeden Fall : Denn es ist ja auch ein Teiler von mit , und würde im Widerspruch dazu stehen, dass kleinster Primfaktor von ist, denn der kleinste Primfaktor von ist ja auch ein Primteiler von und auf jeden Fall kleiner als . Damit folgt und somit . Wenn man also alle Primzahlen checkt, ob sie Teiler von sind, dann muss man irgendwann auf stoßen. Sollte das nicht der Fall sein, d.h. wenn man unter all diesen keinen findet mit , dann bedeutet das zwangsläufig, dass die Annahme (*) falsch war, somit doch Primzahl ist. Wenn man außer Primzahlen zusätzlich auch noch andere Zahlen hinsichtlich dieser Teilbarkeit testet, dann ist das nicht verkehrt, aber eben unnötig. |
|
|
|
Hallo Hal, Danke für die wie immer ausführliche Antwort. Es dauert immmer sehr lange, bis bei mir der Groschen fällt ;-) Für einen Mathematiker wie dich mit jahrzehntelanger Erfahrung ist das natürlich alles trivial :-) "Betrachte doch die Primfaktorzerlegung von und da den KLEINSTEN Primfaktor . Annahme: ist keine Primzahl. Dann muss sein" Wieso muss dann sein? Hier hapert es schon... Eine Primzahl hat ja nur die trivialen Teiler 1 und . (da die 1 per Definition keine Primzahl ist, ist der kleinste Primfaktor natürlich . wenn Primzahl, dann ist der KLEINSTE Primfaktor . Warum jetzt aber wenn keine Primzahl? |
|
|
|
> Wieso muss dann sein? Hier hapert es schon... Oje, wenn hier schon die Probleme beginnen... Dass keine größeren Teiler als besitzen kann, muss ich hoffentlich nicht auch noch begründen, sonst renne ich gleich schreiend davon. Es ist also . Der Fall bedeutet, dass Primzahl ist, was wir per Annahme (*) ja ausgeschlossen haben, also bleibt nur . Am besten vergessen wir das ganze - wenn du in dem Stil bei jeder Trivialität erneut fragst, statt mal selbst zu denken, dann werden wir hier ewig nicht fertig. |
|
|
|
Hallo Hal, Ich glaube ich hab es jetzt schon besser verstanden... wobei der kleinste Primfaktor ist und dessen Komplementärteiler. Beispielsweise selbst kann ja auch wieder in Primfaktoren zerlegt werden. Ich finde also auch da einen kleinsten Primfaktor und kann darstellen als Beispielsweise und Da ja der kleinste Primfaktor in der Primfaktorzerlegung von ist (Annahme), kann der kleinste Primfaktor bei der Zerlegung von ja nicht kleiner sein als . Es gilt also: und da ja (also mit einem multipliziert wird was ja immer größer 1 ist) ist ja auch und damit Also gilt Ich hoffe bis hierher habe ich es richtig verstanden. |
|
|
|
Hallo Hal, ich nochmal :-) Eine (nicht ganz formale) Begründung warum es reicht Primzahlen zu prüfen wäre doch folgende: Wenn keine Primzahl ist, kann ich ja darstellen als Da entweder a oder immer sind und ich ja jede Zahl als Produkt von Primzahlen darstellen kann muss also auch mindestens einer der (Prim)Faktoren sein. Wäre das so richtig gedacht? |
|
|
|
Ja, so rum geht es auch: Man betrachtet irgendeinen Primteiler des kleineren der beiden Faktoren . |
|
Diese Frage wurde automatisch geschlossen, da der Fragesteller kein Interesse mehr an der Frage gezeigt hat.
|
1520477
1519266