Sieb der unendlichen Primzahlen von Eratosthenes

Question

Sieb der unendlichen Primzahlen von Eratosthenes

Mathematik
Zahlentheorie

Karl Vossbrinck

Ich verstehe nicht, warum das Sieb des Eratosthenes nicht unendlich viele Primzahlen beweist. Zum Beispiel eliminiert die Zahl 2 1/2 einer unendlichen Anzahl von Zahlen. Die nächste Primzahl, 3, eliminiert 1/3 des Rests, nicht 1/3 aller Zahlen und so weiter. 5 würde 1/5 der verbleibenden Zahlen eliminieren. Warum beweist das nicht unendlich viele Primzahlen? Danke

Elaqqad

Willkommen auf dieser Seite, das Sieb des Eratosthenes beweist nicht selbst die Existenz einer unendlichen Anzahl von Primzahlen, es ist nur ein Weg "ein Algorithmus", um alle Primzahlen zu finden, die kleiner als N sind. Aber wenn Sie das hier beweisen wollen unendlich viele Primzahlen gibt, muss man mit diesem Sieb beweisen, dass es nach jeder k-Iteration immer eine Zahl gibt, die nicht eliminiert wird (das kann man einfach nehmen

N = p_{1} \dots p_{k} + 1

$N=p_1\cdots p_k+1$ aber es ist nicht im Sieb des Eratosthenes enthalten).

Antworten (1)

Sieb der unendlichen Primzahlen von Eratosthenes

Willkommen auf dieser Seite, das Sieb des Eratosthenes beweist nicht selbst die Existenz einer unendlichen Anzahl von Primzahlen, es ist nur ein Weg "ein Algorithmus", um alle Primzahlen zu finden, die kleiner als N sind. Aber wenn Sie das hier beweisen wollen unendlich viele Primzahlen gibt, muss man mit diesem Sieb beweisen, dass es nach jeder k-Iteration immer eine Zahl gibt, die nicht eliminiert wird (das kann man einfach nehmen $N=p_1\cdots p_k+1$ aber es ist nicht im Sieb des Eratosthenes enthalten).

Mario Carneiro · Answer 1

Ihre Argumentation ist absolut richtig. Angenommen, die Primzahlen sind beschriftet $p_1,p_2,\dots.$ Die wichtigste Beobachtung ist, dass verschiedene Primzahlen teilerfremd sind, also die Dichte von Zahlen, die beide teilen $p_1$ Und $p_2$ Ist $\frac1{p_1p_2}$ und ähnlich für andere Teilmengen der Primzahlen (dies kann auch als Folge des chinesischen Restsatzes angesehen werden). Lassen $A_i$ sei die Menge aller natürlichen Zahlen, die keine von teilen $p_1,p_2,\dots,p_i$ . Dann

\begin{aligned} D (A_{0}) & = 1, \\ D (A_{1}) & = D (A_{0}) (1 - \frac{1}{P_{1}}) = \frac{P_{1} - 1}{P_{1}}, \\ D (A_{2}) & = D (A_{1}) (1 - \frac{1}{P_{2}}) = \frac{P_{1} - 1}{P_{1}} \frac{P_{2} - 1}{P_{2}}, \\ \dots \\ D (A_{N}) & = \prod_{ich = 1}^{N} \frac{P_{ich} - 1}{P_{ich}}, \\ \dots \end{aligned}

$\begin{align}d(A_0)&=1,\\ d(A_1)&=d(A_0)\left(1-\frac1{p_1}\right)=\frac{p_1-1}{p_1},\\ d(A_2)&=d(A_1)\left(1-\frac1{p_2}\right)=\frac{p_1-1}{p_1}\frac{p_2-1}{p_2},\\ &\dots\\ d(A_n)&=\prod_{i=1}^n\frac{p_i-1}{p_i},\\ &\dots \end{align}$

Insbesondere, $d(A_n)$ ist ein Produkt aus positiven Zahlen, was positiv ist, so dass $A_n\ne\emptyset$ für jeden $n$ . Wenn es endlich viele Primzahlen gäbe, hätten wir es getan $A_n$ leer, nachdem wir alle Primzahlen getroffen haben, also ist dies ein gültiger Beweis für die Unendlichkeit von Primzahlen.

@ user3141592 Für eine Teilmenge der natürlichen Zahlen $A\subseteq\Bbb N$ , $d(A)$ ist die Dichte der Menge, die man sich als die Wahrscheinlichkeit vorstellen kann, dass eine zufällig ausgewählte ganze Zahl in der Menge enthalten ist $A$ . (Es ist nicht immer klar definiert, aber es ist immer so $A$ periodisch ist, wie in diesem Fall.)
Aber dann würden wir nach Ihrer Argumentation und nach dem Satz von Mertens das als erhalten $n \to \infty$ , $d(A_n)=\frac{1}{e^\gamma \log(n)}$ , die sich von der korrekten Lösung der PNT durch die unterscheidet $e^{-\gamma}$ Faktor, oder?

Sieb der unendlichen Primzahlen von Eratosthenes

Karl Vossbrinck

Elaqqad

Antworten (1)

Mario Carneiro

Benutzer3141592

Mario Carneiro

Benutzer3141592

Primitiver pythagoreischer Dreifachgenerator

Beweisen Sie diese Identität mit der Triple Product Identity von Jacobi

Gibt es beliebig lange Primzahllücken, in denen jede Zahl mindestens drei verschiedene Primfaktoren hat?

Beweis eines geringfügigen Anspruchs im Zusammenhang mit der Twin Primes-Vermutung

Beziehung zwischen Dirichlets Approximationssatz und Konvergenten

Annäherung einer reellen Zahl um einen Bruchteil von einer Seite

Ein Beweis, dass Zweierpotenzen nicht als Summe mehrerer aufeinanderfolgender positiver Ganzzahlen ausgedrückt werden können, die binäre Darstellungen verwenden?

Wie lange hätte Cole gebraucht, um die Faktoren von M67M67M_{67} auf einer Tafel zu multiplizieren?

n!=n!=n! = das Produkt aufeinanderfolgender ganzer Zahlen. [Duplikat]

Anzahl der Ziffern in 8n8n8^n zur Basis 666