Ein Mathematiker sagte mir einmal, das die Differenz zwischen zwei aufeinander folgenden Primzahlen beliebig gross sein könne. Jedoch den Beweis blieb er mir schuldig, ich mag es auch nicht recht glauben. Ich habe durch manuelles suchen in einer Tabelle der Primzahlen bis 100000 zufaellig zwei aufeinander folgende gefunden bei denen die Differenz z.B. 22 ist. Wie würde man z.B. zwei suchen mit einer Distanz von 1000? Das angehängte Bild zeigt wie mir ein Licht aufgeht... ;-)
Z.b. indem man einen Primzahlgenerator programmiert, die Liste speichert und dann die entsprechenden Zahlen raussucht? Schwierig nicht?
Peter Z. schrieb: > Wie würde man z.B. zwei suchen mit einer Distanz von 1000? Wenn Du im Papier suchen willst: die letzten 3 Stellen sind gleich und die 4. verschieden. Beachte Spaltenumbrüche.
Also die Primzahlen werden immer seltener je größer die Zahl. Also in der Menge der natürlichen Zahlen von 1 bis 1000 sind sagen wir n Primzahlen, in der Menge der natürlich Zahlen von 1001 bis 2000 sind m Primzahlen wobei m<n. Da es unendlich viele Primzahlen gibt, wird die "Primzahlendichte" (könnte man verstehen als Anzahl der Primzahlen je zusammenhängenden 1000 natürlichen Zahlen) auch unendlich klein, nicht Null aber eben fast. Damit wird der Abstand zwischen zwei benachbarten Primzahlen immer größer und irgendwann auch sehr groß. Auch größer als 1000 oder 1000000. Ich habe aber noch eine andere Frage: Wenn man verschlüsselt, werden ja zwei große Primzahlen verwendet. Da gibt es aber gar nicht so viele (ich weiß nicht wie viele). Kann es sein, dass viele Schlüssel gleich sind weil die selben Primzahlen verwendet werden? Oder sind große Primzahlen doch noch so häufig, dass wir alle unterschiedliche Schlüssel haben?
Das kann ich dir sofort wiederlegen: Der Abstand kann vielleicht groß sein, aber definitiv nicht beliebig, denn abgesehen von ein paar wenigen Ausnahmen bei den ganz kleinen Primzahlen, muss der Abstand immer geradzahlig sein. Das liegt daran, dass alle Primzahlen (außer 2) ungerade sind (sonst wären sie durch 2 teilbar) und die Summe aus zwei ungeraden Zahlen ergibt immer eine gerade.
Gut, dass du fragst. Ich habe vor kurzem zum Üben einen Primzahlengenerator programmiert, auch bei 100 Millionen ist der Abstand oft recht klein:
Stephan W. schrieb: > Das kann ich dir sofort wiederlegen: Der Abstand kann vielleicht groß > sein, aber definitiv nicht beliebig, Doch der Abstand kann beliebig groß werden: Betrachte die auf n! folgenden Zahlen ab n! + 2 n! + 2 ist ebenso wie n! durch 2 teilbar, also keine Primzahl n! + 3 ist ebenso wie n! durch 3 teilbar, also keine Primzahl n! + 4 ist ebenso wie n! durch 4 teilbar, also keine Primzahl ... n! + n ist ebenso wie n! durch n teilbar, also keine Primzahl Weil zudem n!+k (k=2..n) durch k teilbar ist, aber mit n! eine kleinere natürliche Zahl ebenso durch k teilbar ist, ist n!+k selbst keine Primzahl. Weil n beliebig groß gewählt werden kann gilt dies auch für k, das lückenlos alle Zahlen von 2 bis n durchläuft.
:
Bearbeitet durch User
Johann L. schrieb: > Doch der Abstand kann beliebig groß werden: Ich meine, dass hier ein Missverständnis vorliegt. "Beliebig groß" bedeutet für mich, ich kann eine beliebige Zahl wählen und werde dafür zwei aufeinanderfolgende Primzahlen finden, die genau diesen Abstand haben. Das habe ich aber oben wiederlegt. Es gibt keine zwei Primzahlen im Abstand 1001 weil alle Primzahlen größer 2 ungerade sind und die Summe zweier ungeraden Zahlen eine gerade ergibt. Was du meinst sind Primzahlen mit einem Abstand, der größer ist als eine beliebige Zahl.
@Stephan W.: Mit beliebig groß meinte ich, dass wenn du mir eine beliebige Zahl nennst, ich dir zwei Primzahlen mit einem größeren Abstand als diese Zahl nennen kann. (kann ich selbst natürlich nicht, aber ist theoretisch möglich)
Das glaube ich natürlich sofort. Johann hat auch schon den Beweis dafür erbracht. Jetzt muss Peter nur noch mal klarstellen, welche Variante er genau meinte ;)
Gustl B. schrieb: > Mit beliebig groß meinte ich, dass wenn du mir eine beliebige Zahl > nennst, ich dir zwei Primzahlen mit einem größeren Abstand als diese > Zahl nennen kann. DAS wiederum ist nicht so einfach. Der von mir skizzierte Beweis (und ähnliche) zeigen lediglich, dass es keine obere Grenze für Intervalle natürlicher Zahlen gibt, die keine Primzahlen enthalten. Um zu zeigen, dass die Lücke zwischen Primzahlen beliebig groß werden kann, genügt dies aber nicht! Erst wenn man hinzunimmt, dass es unendlich viele Primzahlen gibt — was bereits in der Antike bewiesen wurde — folgt, dass Primzahllücken nicht nach oben beschränkt sind. Allerdomgs folgt aus dem Beweis kein Rezept, wie denn zwei solche Primzahlen genau auszusehen haben oder wie sie zu konstruieren wären. Um die Primzahlen zu "nennen", wie du es nennst, gibt es nur einen Weg: Suchen Gesucht wird z.B. von n!+1 abwärts und von n!+n+1 aufwärts (für eine Lücke von mindestens n-1), indem für Zahlen, die einen Pseudoprimzahl-Test bestehen, bewiesen wird, dass sie tatsächlich Primzahl sind (z.B. per Goldwasser-Kilian-Atkin oder Pocklington). https://en.wikipedia.org/wiki/Elliptic_curve_primality
Also ich hatte oben geschrieben: "Da es unendlich viele Primzahlen gibt, ..." Das hatte ich also vorausgesetzt.
Ey gibt doch wahrscheinlich auch unendlich viele Primzahlpaare dann kann der Abstand ja nicht unendlich groß werden irgendwann ist er doch wieder 2
Ansgar K. schrieb: > Ey gibt doch wahrscheinlich auch unendlich viele Primzahlpaare dann kann > der Abstand ja nicht unendlich groß werden irgendwann ist er doch wieder > 2 Wenn ich es richtig verstanden habe, wächst der maximale Abstand zwischen zwei Primzahlen. Das sagt aber nichts über den minimalen Abstand aus.
Stephan W. schrieb: > Ich meine, dass hier ein Missverständnis vorliegt. "Beliebig groß" > bedeutet für mich, ich kann eine beliebige Zahl wählen und werde dafür > zwei aufeinanderfolgende Primzahlen finden, die genau diesen Abstand > haben. Dann liegt der Fehler bei dir. Im mathematischen Kontext bedeutet beliebig groß nämlich etwas anderes. Korrekt formuliert würde es heißen "es existiert keine untere Schranke für die Differenz zweier aufeinander folgender Primzahlen". Das was du in die Formulierung "beliebig groß" hinein interpretierst, würde mathematisch ungefähr so formuliert werden: "für jede natürliche Zahl n existiert ein Paar aufeinander folgender Primzahlen, deren Differenz gleich n ist". Aus offensichtlichen Gründen wäre diese Behauptung falsch - denn es existiert nur ein einziges Primzahlpaar, dessen Differenz ungerade ist.
Axel S. schrieb: > "es existiert keine untere Schranke für die Differenz zweier > aufeinander folgender Primzahlen". Du meinst wohl "obere Schranke". Die unter Schranke ist 1.
Uhu U. schrieb: > Axel S. schrieb: >> "es existiert keine untere Schranke für die Differenz zweier >> aufeinander folgender Primzahlen". > > Du meinst wohl "obere Schranke". Die unter Schranke ist 1. Ja, er meint natürlich "obere Schranke", also: Für jede vorgegebene (natürliche) Zahl n existieren zwei aufeinander folgende Primzahlen, deren Differenz mindestens n ist. Übrigens gibt es nicht die untere Schranke. 0 und -1 und -1.7 sind auch untere Schranken für Primnachbar-Abstände. Allerdings gibt es eine größte untere Schranke — genannt "Infimum" — und dieses ist dann tatsächlich eindeutig (und ist im vorliegenden Falle 1). https://de.wikipedia.org/wiki/Infimum_und_Supremum Die Definition von "Infimum" und "Supremum" ist etwas technisch; anschaulich übernehmen Supremum und Infimum bei unendlichen, geordneten Mengen die Rolle, welche Maximum und Minimum bei endlichen, geordneten Mengen haben. So hat die Menge aller 1/n für n in N kein Minimum sondern lediglich ein Infimum: 0.
Johann L. schrieb: > Übrigens gibt es nicht die untere Schranke. 0 und -1 und -1.7 sind > auch untere Schranken für Primnachbar-Abstände. Teilbarkeit macht für natürliche Zahlen Sinn, höchstens für ganze Zahlen, aber diese Erweiterung bringt keine neue Erkenntnis, die Sache ist symmetrisch und die -1.7 ist da nicht dabei. Nenn es größte untere Schranke, dann paßt es. Der Begriff des Infimums auf N angewandt ist identisch mit der größten unteren Schranke - die Verkomplizierung/Verallgemeinerung des Begriffes bringt hier nichts.
:
Bearbeitet durch User
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.