Unendl.viele Primzahlen modulo

16.04.2009, 14:57

Eul-Er

Unendl.viele Primzahlen modulo

Hallo,
Wie beweise ich, dass es unendlich viele Primzahlen p mit p=1mod3 gibt? Mit dem Beweis von Euklid (für "Es gibt unendlich viele Primzahlen") klappt es nicht so richtig.

Danke.

18.04.2009, 13:26

Abakus

Auf diesen Beitrag antworten »

RE: Unendl.viele Primzahlen modulo
Versuche doch mal, den klassischen Beweis auf Primzahlen des Typs $\begin{eqnarray*} (3k+1) \end{eqnarray*}$ zu erweitern. Wo steckst du da fest?

Grüße Abakus smile

19.04.2009, 15:58

Eul-Er

Auf diesen Beitrag antworten »

RE: Unendl.viele Primzahlen modulo
Ok,
nach dem klassischen Beweis gehe ich davon aus, dass es nur endlich viele k gibt, für die (3k+1) eine Primzahl ist und zeige, dass es dann noch eine Primzahl gibt, die sich so darstellen lässt. Soweit klar. Aber ist mit $\begin{eqnarray*} 3((3k_{1}+1)*...*(3k_{n}+1))+1=Primzahl \end{eqnarray*}$ der Beweis schon erledigt oder bin ich auf dem Holzweg?

19.04.2009, 20:00

Elvis

Auf diesen Beitrag antworten »

Ja,Holzweg !
3*7+1=22, 3*7*13+1=274, ...
und noch viel schlimmer: 3*(ungerade)+1=gerade !!!

20.04.2009, 11:35

Eul-Er

Auf diesen Beitrag antworten »

Leuchtet ein. Und wie sähe der bessere Weg aus?

20.04.2009, 11:47

Auf diesen Beitrag antworten »

Die Sache ist nicht ganz so einfach, zumindest ist das mein erster Eindruck.

Bei Primzahlen der Form $\begin{eqnarray*} 3k+2 \end{eqnarray*}$ kann man den Euklid-Beweis leicht übertragen:

Angenommen, es gibt nur endlich viele Primzahlen der Form $\begin{eqnarray*} 3k+2 \end{eqnarray*}$ , diese bilden die Menge $\begin{eqnarray*} M \end{eqnarray*}$ . Dann betrachtet man

$\begin{eqnarray*} n = 6\prod\limits_{p\in M} p ~ - ~ 1 \end{eqnarray*}$ .

Die Annahme, dass die ungerade und nicht durch 3 teilbare Zahl n nur Primteiler der Form $\begin{eqnarray*} 3k+1 \end{eqnarray*}$ hat, führt zum Widerspruch, da ein Produkt solcher Primteiler ebenfalls die Form $\begin{eqnarray*} 3k+1 \end{eqnarray*}$ hat, $\begin{eqnarray*} n \end{eqnarray*}$ aber nicht!

--------------------

Für $\begin{eqnarray*} 3k+1 \end{eqnarray*}$ scheitert dieser einfache Weg, da muss es noch einen anderen Dreh geben...

20.04.2009, 14:40

Reksilat

Auf diesen Beitrag antworten »

Arthur hat's auch nicht raus Tanzen

Woher kommt denn die Aufgabe? Ich habe mir die Fragestellung zuletzt hin und wieder durch den Kopf gehen lassen und keine elementare Lösung gefunden. Die Aufgabe legt ja schließlich nahe, dass der Aufwand etwas geringer ist, als für den Beweis des Dirichlet.

Gruß,
Reksilat.

20.04.2009, 14:55

Auf diesen Beitrag antworten »

Nun, wenn ich mit dem Zugeben meines Scheiterns was erreicht habe, dass sich andere aus der Deckung wagen. Big Laugh

20.04.2009, 15:44

Huggy

Auf diesen Beitrag antworten »

In dem Buch von Ribenboim über Primzahlen gibt es den Hinweis, dass sich der Fall 3k + 1 und einige weitere arithmetische Folgen mittels einfacher Eigenschaften quadratischer Reste beweisen lassen.

Das ist nicht mein Metier, aber vielleicht bringt es jemanden auf den zündenden Gedanken.

20.04.2009, 15:54

Auf diesen Beitrag antworten »

Ich war gerade in derselben Richtung unterwegs - mit ein wenig googeln (oder heißt es googlen?) findet man eine Idee, basierend auf dem quadratischen Reziprozitätsgesetz (QR):

------------------
Ist $\begin{eqnarray*} n^2\equiv -3\mod p \end{eqnarray*}$ für eine Primzahl $\begin{eqnarray*} p>3 \end{eqnarray*}$ , so gilt $\begin{eqnarray*} p\equiv 1\mod 6 \end{eqnarray*}$

Begründung: Mit den Legendresymbolen und QR ergibt sich

$\begin{eqnarray*} \left( \frac{-3}{p} \right) = \left( \frac{-1}{p} \right) \cdot \left( \frac{3}{p} \right) = (-1)^{\frac{p-1}{2}} \cdot (-1)^{\frac{p-1}{2}\cdot \frac{3-1}{2}} \cdot \left( \frac{p}{3} \right) = \left( \frac{p}{3} \right) = \begin{cases} 1 & \;\mbox{für}\; p\equiv 1\mod 6\\ -1 & \;\mbox{für}\; p\equiv -1\mod 6 \end{cases} \end{eqnarray*}$ .
------------------

Dann nimmt man wieder an, es gäbe nur endlich viele Primzahlen der Form $\begin{eqnarray*} 6k+1 \end{eqnarray*}$ , vereinigt in der Menge $\begin{eqnarray*} M \end{eqnarray*}$ , und bildet daraus nun

$\begin{eqnarray*} n = \left( 2\prod\limits_{p\in M} p \right)^2 + 3 \end{eqnarray*}$ .

Mit obiger Hilfsaussage ergibt sich dann ein Widerspruch.

20.04.2009, 17:30

Reksilat

Auf diesen Beitrag antworten »

Schön!

20.04.2009, 22:35

Abakus

Auf diesen Beitrag antworten »

Ich versuchs mal etwas anders, aber doch ähnlich zu Arthur:

Zunächst reicht es, die Behauptung für Zahlen des Typs $\begin{eqnarray*} (6k + 1) \end{eqnarray*}$ zu zeigen. Seien nun $\begin{eqnarray*} 6k_1+1,~ ..., 6k_n+1 \end{eqnarray*}$ alle Primzahlen dieses Typs.

Setze nun:

$\begin{eqnarray*} q := (6k_1+1) \cdot~ ...~\cdot (6k_n+1) \end{eqnarray*}$ ;

und

$\begin{eqnarray*} z := (6q)^2 + 6q + 1 \end{eqnarray*}$ .

$\begin{eqnarray*} z \end{eqnarray*}$ selbst ist nach Konstuktion eine Zahl der Bauart $\begin{eqnarray*} 6k+1 \end{eqnarray*}$ . Ist $\begin{eqnarray*} z \end{eqnarray*}$ eine Primzahl, haben wir eine weitere Zahl dieser Bauart gefunden und sind fertig.

Ist $\begin{eqnarray*} z \end{eqnarray*}$ keine Primzahl, so sei $\begin{eqnarray*} p \ne z \end{eqnarray*}$ ein echter Teiler von z, also: $\begin{eqnarray*} p~ |~ z \end{eqnarray*}$ . Natürlich ist p dann konstruktionsgemäß verschieden von den obigen Primzahlen $\begin{eqnarray*} 6k_1+1,~ ..., 6k_n+1 \end{eqnarray*}$ .

Wegen $\begin{eqnarray*} z \cdot (6q - 1) = (6q)^3 - 1 \end{eqnarray*}$ folgt nun sofort $\begin{eqnarray*} (6q)^3 \equiv 1 ~mod~ p \end{eqnarray*}$ .

Modulo p betrachtet gibt es jetzt 2 Möglichkeiten zu untersuchen:

- es gelte $\begin{eqnarray*} 6q \equiv 1~mod~ p \end{eqnarray*}$ , in diesem Fall wäre $\begin{eqnarray*} z \equiv (1 + 1 + 1)~mod~ p \end{eqnarray*}$ und damit $\begin{eqnarray*} p=3 \end{eqnarray*}$ . Da $\begin{eqnarray*} z \end{eqnarray*}$ nicht durch 3 teilbar ist, folgt ein Widerspruch.

- es ist $\begin{eqnarray*} 6q \not\equiv 1~mod~ p \end{eqnarray*}$ . Damit hat $\begin{eqnarray*} (6q) \in \mathbb Z_p^* \end{eqnarray*}$ die Ordnung 3, diese muss die Gruppenordnung $\begin{eqnarray*} \varphi(p) = p-1 \end{eqnarray*}$ teilen, also $\begin{eqnarray*} 3~|~(p-1) \end{eqnarray*}$ . Da $\begin{eqnarray*} (p-1) \end{eqnarray*}$ gerade ist, gilt auch $\begin{eqnarray*} 6~|~(p-1) \end{eqnarray*}$ und damit existiert ein $\begin{eqnarray*} m \end{eqnarray*}$ mit $\begin{eqnarray*} p = 6m + 1 \end{eqnarray*}$ , was zu zeigen war.

Grüße Abakus smile

21.04.2009, 09:17

Auf diesen Beitrag antworten »

Gefällt mir, vor allem weil es ohne den doch nicht ganz so elementaren QR auskommt. Freude

21.04.2009, 17:14

Eul-Er

Auf diesen Beitrag antworten »

Gut, vielen Dank. Für die erste Aufgabe einer Zahlentheorie-Vorlesung ist der Beweis ganz schön heavy. Einzig mit Euklid lässt sich da wohl nix machen.

Für Arthur Dent: hast du dich in deinem Beweis für 2mod3 etwas vertippt und meintest statt 3k+1 vielleicht 3k+2 (in den letzten beiden Zeilen deines Beweises)?

Viele Grüße,
E-E.

21.04.2009, 17:24

Auf diesen Beitrag antworten »

Nein, nicht vertippt - wieso?

21.04.2009, 17:43

Eul-Er

Auf diesen Beitrag antworten »

Weil ein Produkt von Primzahlen der Form 3k+2 auch die Form 3k+2 hat, und nicht 3k+1. (Nimm 5, 11, 17)

21.04.2009, 18:01

Auf diesen Beitrag antworten »

$\begin{eqnarray*} 5\cdot 11 = 55 = 3\cdot 18 +1 \end{eqnarray*}$ .

Soviel dazu.

21.04.2009, 18:09

Eul-Er

Auf diesen Beitrag antworten »

Ja okay, aber was ist mit $\begin{eqnarray*} 5*11*17=935=3*311+2 \end{eqnarray*}$ ?

21.04.2009, 18:11

Auf diesen Beitrag antworten »

Arrggghh, ich hab befürchtet, dass so was kommt. Finger1

Ein Beispiel beweist keine Aussage - ein Gegenbeispiel widerlegt sie aber!

Nun schau dir mal deine Aussage

Zitat:

Original von Eul-Er
Weil ein Produkt von Primzahlen der Form 3k+2 auch die Form 3k+2 hat

in dieser Hinsicht an.

Und überhaupt ist mir völlig rätselhaft, inwiefern das gegen meine Argumentation

Zitat:

Original von Arthur Dent
$\begin{eqnarray*} n = 6\prod\limits_{p\in M} p ~ - ~ 1 \end{eqnarray*}$ .

Die Annahme, dass die ungerade und nicht durch 3 teilbare Zahl $\begin{eqnarray*} n \end{eqnarray*}$ nur Primteiler der Form $\begin{eqnarray*} 3k+1 \end{eqnarray*}$ hat, führt zum Widerspruch, da ein Produkt solcher Primteiler ebenfalls die Form $\begin{eqnarray*} 3k+1 \end{eqnarray*}$ hat, $\begin{eqnarray*} n \end{eqnarray*}$ aber nicht!

sprechen soll? verwirrt

21.04.2009, 18:26

Eul-Er

Auf diesen Beitrag antworten »

Ahso, hast recht. Lesen sollte man auch als Mathematikstudent können. Sorry und danke nochmals.

Neue Frage »

Antworten »

Unendl.viele Primzahlen modulo

Verwandte Themen