Primzahl

11.11.2013, 18:03

Lynn2

Primzahl

Meine Frage:
Zeigen Sie: Es gibt unendlich viele Primzahlen der Form $\begin{eqnarray*} 4n-1, n\in \mathbb N \end{eqnarray*}$ .

Meine Ideen:
Ich denke, dass es nicht vom Vorteil ist, wenn man dies anhand einer vollständigen Induktion zeigt. Ein Gegenbeispiel fällt ja auch flach.

Kann man dies anhand eines indirekten Beweises lösen?

Annahme: Es gibt nur endlich viele Primzahlen der Form $\begin{eqnarray*} 4n-1, n\in \mathbb N \end{eqnarray*}$ .
Nun jedoch weiß ich nicht weiter. Hättet ihr einen Tipp für mich?

11.11.2013, 18:14

tmo

Auf diesen Beitrag antworten »

Man muss eigentlich nur den Beweis von Euklid nachäffen und minimal anpassen.

11.11.2013, 18:31

Lynn2

Auf diesen Beitrag antworten »

RE: Primzahl
Annahme: Es gibt nur endlich viele Primzahlen der Form $\begin{eqnarray*} p_n=4n-1, n\in \mathbb N \end{eqnarray*}$ , wobei $\begin{eqnarray*} p \end{eqnarray*}$ die Primzahl ist.

endlich viele Primzahlen: $\begin{eqnarray*} p_1<...<p_n, n\in \mathbb N \end{eqnarray*}$
Nun ist aber auch b eine mögliche Lösung und b ist eine Primzahl. Und da $\begin{eqnarray*} p_n < b \end{eqnarray*}$ - Widerspruch.

Ist das so in Ordnung? Oder gibt es da noch was zu verbessern?

11.11.2013, 18:36

tmo

Auf diesen Beitrag antworten »

Was ist b? verwirrt

11.11.2013, 18:37

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Lynn2
Nun ist aber auch b eine mögliche Lösung und b ist eine Primzahl. Und da $\begin{eqnarray*} p_n < b \end{eqnarray*}$

Aha, du sollst beweisen, dass es so ein b gibt, und da sagst (ohne Begründung): Es existiert - Beweis fertig.

Ich hoffe mal stark, du glaubst nicht selbst an diesen Beweis, das wäre ja Selbsttäuschung höchsten Ausmaßes. tmo hat auf den Beweis von Euklid verwiesen, hast du da wirklich drüber nachgedacht?

11.11.2013, 18:49

Lynn2

Auf diesen Beitrag antworten »

In der Vorlesung haben wir es so begonnen: (Euklid)

indirekter Beweis:
Annahme: Es gibt endlich viele Primzahlen p.

$\begin{eqnarray*} p_1<...<p_n, n\in \mathbb N \end{eqnarray*}$
$\begin{eqnarray*} m = p_1 \cdot ... \cdot p_n + 1 \end{eqnarray*}$

Und nun habe ich für m einfach b eingesetzt. Darf ich das nicht machen?

11.11.2013, 18:54

HAL 9000

Auf diesen Beitrag antworten »

Darfst du nicht: Zum einen ist dieses so konstruierte m nicht notwendig eine Primzahl. Und selbst wenn - wo ist die Begründung, dass es eine Primzahl vom Typ 4n-1 ist?

EDIT: Tatsächlich ist $\begin{eqnarray*} m = p_1 \cdot ... \cdot p_n + 1 \end{eqnarray*}$ sogar sicher eine gerade Zahl, wenn die $\begin{eqnarray*} p_k \end{eqnarray*}$ alle vom Typ $\begin{eqnarray*} 4n-1 \end{eqnarray*}$ sind, also sicher keine Primzahl.

11.11.2013, 19:08

Lynn2

Auf diesen Beitrag antworten »

Okay, dann fangen wir nochmal an:

indirekter Beweis:
Annahme: Es gibt endlich viele Primzahlen p.

$\begin{eqnarray*} p_1<...<p_n, n\in \mathbb N \end{eqnarray*}$
$\begin{eqnarray*} m = p_1 \cdot ... \cdot p_n + 1 \end{eqnarray*}$

1. Fall: $\begin{eqnarray*} m \end{eqnarray*}$ ist eine Primzahl $\begin{eqnarray*} \Rightarrow m > p_n \end{eqnarray*}$ - Widerspruch
2. Fall: $\begin{eqnarray*} m \end{eqnarray*}$ ist keine Primzahl $\begin{eqnarray*} \Rightarrow m \end{eqnarray*}$ besitzt einen Primfaktor q, dieses q müsste somit eine der Primzahlen $\begin{eqnarray*} p_1<...<p_n \end{eqnarray*}$ sein.
$\begin{eqnarray*} q \cdot m = p_1 \cdot ... \cdot q \cdot ... \cdot p_n + 1 \end{eqnarray*}$
$\begin{eqnarray*} q \cdot (m - p_1 \cdot ... \cdot p_n) = 1 \end{eqnarray*}$
Deshalb müsste q Teiler von 1 sein, aber dann ist q kein Primfaktor. Widerspruch.

Ist der Beweis von Euklid so richtig von mir verstanden? Und wie füge ich nun meinen Typ ein?

11.11.2013, 21:05

HAL 9000

Auf diesen Beitrag antworten »

Tja, das wäre nun der kreative Teil...

Ok, wir nehmen an, dass es nur endlich viele Primzahlen $\begin{eqnarray*} p_1,\ldots,p_k \end{eqnarray*}$ vom Typ $\begin{eqnarray*} 4n-1 \end{eqnarray*}$ gibt. Nun betrachten wir aber nicht $\begin{eqnarray*} m=p_1\cdot \ldots \cdot p_k+1 \end{eqnarray*}$ , das wird nix - besser ist $\begin{eqnarray*} m=4\cdot p_1\cdot \ldots \cdot p_k-1 \end{eqnarray*}$ , wir werden sehen warum: Betrachte jetzt nämlich mal die Primfaktorzerlegung von $\begin{eqnarray*} m \end{eqnarray*}$ .

11.11.2013, 21:24

Lynn2

Auf diesen Beitrag antworten »

$\begin{eqnarray*} m\cdot q=4\cdot p_1\cdot \ldots \cdot q \cdot \ldots \cdot p_k-1 \end{eqnarray*}$
$\begin{eqnarray*} 1=4\cdot p_1\cdot \ldots \cdot q \cdot \ldots \cdot p_k-m \cdot q \end{eqnarray*}$
$\begin{eqnarray*} 1=q\cdot (4\cdot p_1\cdot \ldots \cdot p_k-m) \end{eqnarray*}$

Meinst du das?

11.11.2013, 22:05

HAL 9000

Auf diesen Beitrag antworten »

Ich denke da noch an was anderes, wichtiges "Neues" im Vergleich zum Original-Euklid-Beweis - mit bloßem unüberlegten Abpinseln des Beweises ist es eben nicht getan:

Wenn du von $\begin{eqnarray*} q \end{eqnarray*}$ sprichst, dann meinst du also eine Primzahl vom Typ 4n-1, die Teiler von m ist. Woher weißt du, dass es eine solche Primzahl gibt? Schließlich gibt es neben den ungeraden Primzahlen vom Typ 4n-1 auch noch die ungeraden Primzahlen vom Typ 4n+1 - es fehlt also noch eine schlüssige Begründung für die Existenz eines solchen $\begin{eqnarray*} q \end{eqnarray*}$ .

11.11.2013, 22:13

Lynn2

Auf diesen Beitrag antworten »

Da in der Aufgabe ja der Typ 4n-1 gefordert ist, kann ich doch $\begin{eqnarray*} m\cdot q=m\cdot (4n-1) \end{eqnarray*}$ setzen oder?

11.11.2013, 23:11

HAL 9000

Auf diesen Beitrag antworten »

Ok, dann frage ich mal so:

Meinst du, der obige Beweis funktioniert auch mit $\begin{eqnarray*} m=4\cdot p_1\cdot \ldots \cdot p_k{\color{red}+}1 \end{eqnarray*}$ ?

12.11.2013, 13:29

Lynn2

Auf diesen Beitrag antworten »

Nein, da beispielsweise $\begin{eqnarray*} m=4\cdot2\cdot3+1=25 \end{eqnarray*}$ .

12.11.2013, 23:01

HAL 9000

Auf diesen Beitrag antworten »

Genau, d.h. dieses andere $\begin{eqnarray*} m \end{eqnarray*}$ hat nicht notwendig einen Primteiler der Form $\begin{eqnarray*} 4n-1 \end{eqnarray*}$ . Warum ist dies aber bei $\begin{eqnarray*} m=4\cdot p_1\cdot \ldots \cdot p_k-1 \end{eqnarray*}$ der Fall - dafür habe ich noch keine überzeugende Begründung von dir gehört.

Neue Frage »

Antworten »

Primzahl

Verwandte Themen