Zahlentheorie, Möglichkeiten

14.11.2012, 15:36

mago12

Zahlentheorie, Möglichkeiten

Hallo!

Sei $\begin{eqnarray*} \pi(n) \end{eqnarray*}$ die Anzahl der Primzahlen $\begin{eqnarray*} \leq n \end{eqnarray*}$ . Sei $\begin{eqnarray*} m \in \{1,2,...,n\} \end{eqnarray*}$ eine natürliche Zahl, welche man in der Form $\begin{eqnarray*} m=a^2 \cdot b \end{eqnarray*}$ schreibt. b soll quadratfrei sein, a,b natürliche Zahlen.

Warum gibt es für b dann höchstens $\begin{eqnarray*} 2^{\pi(n)} \end{eqnarray*}$ Möglichkeiten? Das ist ja eine Abschätzung der quadratfreien Zahlen $\begin{eqnarray*} \leq n \end{eqnarray*}$ .

14.11.2012, 15:45

HAL 9000

Auf diesen Beitrag antworten »

Einerseits ist $\begin{eqnarray*} b\leq n \end{eqnarray*}$ , d.h. $\begin{eqnarray*} b \end{eqnarray*}$ enthält als Primfaktoren nur Primzahlen $\begin{eqnarray*} p\leq n \end{eqnarray*}$ . Andererseits enthält es jeden dieser Primfaktoren $\begin{eqnarray*} p \end{eqnarray*}$ wegen der Quadratfreiheit aber auch höchstens einmal, d.h. als Primzahlpotenz betrachtet entweder $\begin{eqnarray*} p^0 \end{eqnarray*}$ oder $\begin{eqnarray*} p^1 \end{eqnarray*}$ ...

P.S.: Ich frag mich allerdings nach dem Nutzen dieser Abschätzung: Mit $\begin{eqnarray*} \pi(n)\sim \frac{n}{\ln(n)} \end{eqnarray*}$ ist ja $\begin{eqnarray*} 2^{\pi(n)} \end{eqnarray*}$ weit größer als $\begin{eqnarray*} n \end{eqnarray*}$ , was ja auch eine triviale obere Schranke für $\begin{eqnarray*} b \end{eqnarray*}$ ist. verwirrt

14.11.2012, 15:45

tmo

Auf diesen Beitrag antworten »

RE: Zahlentheorie, Möglichkeiten

Zitat:

Original von mago12
Warum gibt es für b dann höchstens $\begin{eqnarray*} 2^{\pi(n)} \end{eqnarray*}$ Möglichkeiten? Das ist ja eine Abschätzung der quadratfreien Zahlen $\begin{eqnarray*} \leq n \end{eqnarray*}$ .

Die Antwort hast du doch im Satz dahinter selbst gegeben.

Eine quadratfreie Zahl ist das Produkt paarweiser verschiedener Primzahlen. Da wir hier höchstens $\begin{eqnarray*} \pi(n) \end{eqnarray*}$ verschiedene Primzahlen zur Auswahl haben, können wir im besten Fall für jede Primzahl entscheiden, ob sie als Faktor vorkommt oder eben nicht. Das ergibt dann $\begin{eqnarray*} 2^{\pi(n)} \end{eqnarray*}$ .

Diese Abschätzung ist sehr sehr grob. Im Allgemeinen sind nämlich die wenigsten dieser $\begin{eqnarray*} 2^{\pi(n)} \end{eqnarray*}$ Produkte auch wirklich kleinergleich $\begin{eqnarray*} n \end{eqnarray*}$ . Für einfache Zwecke (wie den Beweis der Unendlichkeit der Primzahlen oder den Beweis, dass die Summe der reziproken Primzahlen divergiert) reicht sie aber aus.

edit: @HAL: Großen Nutzen hat die Schranke natürlich nicht, sobald man etwas mehr Einblicke hat.

Immerhin liefert diese Schranke in Verbindung damit, dass die Anzahl der Quadrate kleinergleich $\begin{eqnarray*} n \end{eqnarray*}$ durch $\begin{eqnarray*} \sqrt{n} \end{eqnarray*}$ beschränkt sind, schonmal die Abschätzung $\begin{eqnarray*} 2^{\pi(n)} \sqrt{n} \geq n \end{eqnarray*}$ , was die Unbeschränktheit von $\begin{eqnarray*} \pi \end{eqnarray*}$ und damit die Unendlichkeit der Primzahlen zeigt. Wir sehen mal davon ab, dass sich Euklid bei solch einem Beweis im Grabe umdrehen würde Big Laugh

14.11.2012, 15:59

HAL 9000

Auf diesen Beitrag antworten »

@tmo

Hatte deinen Beitrag noch nicht gelesen, ansonsten hätte ich mir das nachgeschobene P.S. gespart. Augenzwinkern

14.11.2012, 16:03

tmo

Auf diesen Beitrag antworten »

Und ich wiederum habe deinen letzten Beitrag nicht gelesen, sonst hätte ich mir mein weiteres Edit gespart smile

Neue Frage »

Antworten »

Zahlentheorie, Möglichkeiten

Verwandte Themen