Noch ein einfaches Primzahlsieb

Question

Denke dir eine Tabelle mit unendlich vielen Zeilen und Spalten. Die k-te Zeile (ebenso die k-te Spalte) wird von einer arithmetischen Folge gebildet, die das Startglied 6k+3 und die konstante Differenz 4k+2 hat. Der Anfang der Tabelle sieht also so aus:

  9 15 21 27 ...
15 25 35 45 ...
21 35 49 63 ...
27 45 63 81 ...
... ... ... ... ...
Zeige: Alle ungeraden natürlichen Zahlen außer 1, die nicht in dieser Tabelle vorkommen, sind Primzahlen und so sind alle Primzahlen beschrieben.

Answer 1

Behauptung: Die Zahlen in der $k$-ten Zeile sind alle ungeraden natürlichen Zahlen welche durch $2k+1$ teilbar und echt größer als $2k+1$ sind.

Beweis:

1. Sei $n$ eine Zahl in der $k$-ten Zeile, dann existiert ein $m \ge 0$ s.d. $$n = 6k+3 + m (4k+2) = (2k+1)\underbrace{(3+2m)}_{>1}$$

Also sind alle Zahlen in der $k$-ten Zeile durch $2k+1$ teilbar und echt größer als $2k+1$. Insbesondere enthält jeder Eintrag der Tabelle einen echten Teiler und ist somit zusammengesetzt.

2. Ist hingegen $n$ eine ungerade natürliche Zahl, welche durch $2k+1$ teilbar und echt größer als $2k+1$ ist, dann existiert ein $m \ge 2$ mit $n = (2k+1)m$. Da $n$ ungerade ist muss auch $m$ ungerade sein, insbesondere ist $m \ge 3$. $m - 3 \ge 0$ ist also eine gerade Zahl und wir finden ein $l \in \mathbb N_0$ mit $m-3 = 2l$ bzw. $m = 3+2l$. Insgesamt erhalten wir $$n = (2k+1)(3+2l) = (6k+3) + l (4k+2)$$ weshalb $n$ in der $k$-ten Zeile auftauchen muss.

---

Damit folgen alle Aussagen:

Aus Teil 1 des Beweises folgt direkt, dass keine Primzahl in der Tabelle liegt.

Ist hingegen $n$ eine ungerade Zahl, welche nicht prim ist, dann hat $n$ einen echten ungeraden Teiler - etwa $2k+1$ - und taucht nach Teil 2 des Beweises auf jeden Fall in der $k$-ten Zeile der Tabelle auf.

Comments

Es wäre auch eine etwas kürzere Formulierung möglich gewesen. Vor allem der letzte Absatz ist entscheidend für die Auszeichnung als "Beste".