Unendlich viele Primzahlen - Beweis nach Euklid

23.11.2009, 20:41

Arizona

Unendlich viele Primzahlen - Beweis nach Euklid

Ich soll zeigen, dass es unendlich viele Primzahlen der Form p=4n+3 gibt und dazu Euklids Beweisidee benutzen - wie kann ich denn hierbei vorgehen? Den Beweis mit einer einfachen Variable p (nach Euklid) habe ich verstanden, für eine Menge an Primzahlen nehme ich ja p_1, p_2, p_3, ..., p_m an. Aber wie kann ich das nun hier machen? 4n_1+3, 4n_2+3, ..., 4n_m+3 vielleicht?

22.06.2012, 21:05

Darthtidus

Auf diesen Beitrag antworten »

Euklid Beweis nachvollziehen wollen
Wie kann man den Beweis von Euklid nachvollziehen?

Angenommen, es gäbe nur endlich viele Primzahlen p1, p2,...ps. Dann ist p1*p2*...*ps+1 eine natürliche Zahl > 1. Diese muss durch eine Primzahl p teilbar sein. Da p verschieden von p1, p2,...ps ist, ist p eine neue Primzahl.

Nehme ich diese zum Beispiel die ersten Primzahlen und sage 11 = ps:

2,3,5,7,11. Laut Satz ist ps+1, in unserem Fall 2*3*5*7*11+1=2311 eine natürliche Zahl größer 1. Warum muss diese jetzt durch p teilbar sein und nicht durch p1, oder p2 oder ps? (also 12 durch 2, pder 3 oder...)?

Das leuchtet mir jetzt nicht ein.

Wenn jemand einen Rat hat, wäre ich für euer Feedback dankbar.

LG

Darthtidus

22.06.2012, 22:39

lgrizu

Auf diesen Beitrag antworten »

RE: Euklid Beweis nachvollziehen wollen
Angenommen, es gebe (wie in deinem Beispiel) nur die Primzahlen 2,3,5,7,11.

Wir bilden das Produkt und addieren es mit 1:

2*3*5*7*11+1=2311 und das ist eine Primzahl.

Wir nehmen allgemein an, es gebe nur endlich viele Primzahlen, diese nummerieren wir durch:

$\begin{eqnarray*} P_1, P_2,....,P_n \end{eqnarray*}$

Nun ist nach dem Fundamentalsatz der Zahlentheorie jede natürliche Zahl eindeutig in ein Produkt von Primzahlen zerlegbar (das ist hier wichtig!).

Wir bilden nun die Zahl

$\begin{eqnarray*} q=\prod_{i=1}^{n} P_i +1 \end{eqnarray*}$

Es gibt nun zwei Möglichkeiten, entweder ist q selbst eine Primzahl, oder aber sie ist in ein Produkt von Primzahlen zerlegbar, besitzt also einen Primteiler.

Dieser Primteiler muss einer unserer endlich vielen Primzahlen sein, sagen wir es ist die Zahl $\begin{eqnarray*} P_s \end{eqnarray*}$ .

Nun ist das Produkt $\begin{eqnarray*} \prod_{i=1}^{n} P_i \end{eqnarray*}$ durch $\begin{eqnarray*} P_s \end{eqnarray*}$ teilbar.

Angenommen, q ist auch durch $\begin{eqnarray*} P_s \end{eqnarray*}$ teilbar, dann muss 1 durch $\begin{eqnarray*} P_s \end{eqnarray*}$ teilbar sein, was einen Widerspruch ergibt.

22.06.2012, 23:08

Darthtidus

Auf diesen Beitrag antworten »

Euklid Beweis nachvollziehen wollen
Danke Arizona,

so wie du es erklärt hast, habe ich es sehr gut verstanden.

Ich finde es toll, dass man hier so kompetente Antworten / Lösungen bekommt.

Ich wünsche Dir noch einen schönen Abend.

LG

Darthtidus

23.06.2012, 11:57

lgrizu

Auf diesen Beitrag antworten »

RE: Euklid Beweis nachvollziehen wollen

Zitat:

Original von Darthtidus
Danke Arizona,

Falscher Name? verwirrt

aber nun gut....

Zitat:

Original von Darthtidus
so wie du es erklärt hast, habe ich es sehr gut verstanden.

Ich finde es toll, dass man hier so kompetente Antworten / Lösungen bekommt.

Immer wieder gerne Wink

24.06.2012, 17:41

Mystic

Auf diesen Beitrag antworten »

RE: Euklid Beweis nachvollziehen wollen

Zitat:

Original von lgrizu
Nun ist nach dem Fundamentalsatz der Zahlentheorie jede natürliche Zahl eindeutig in ein Produkt von Primzahlen zerlegbar (das ist hier wichtig!).

Interessanterweise ist es so, dass der notwendige Nachweis, dass eine natürliche Zahl n>1 überhaupt einen Primteiler besitzt, in vielen Beweisen glatt vergessen/nicht gesehen wird... Das kann man dir nun nicht gerade vorwerfen, wohl aber, dass du mit "Kanonen auf Spatzen" schießt, wenn du hier gleich mit dem schweren Geschütz des Fundamentalsatzes der Zahlentheorie in seiner vollen Allgemeinheit auffährst... Augenzwinkern

Tätsächlich geht er aber der Nachweis dafür viel einfacher: Ist nämlich T die Menge aller Teiler t>1 von n, so ist T nichtleer, da es n enthält und p:=min T ein Primteiler von n, da jeder Teiler t von p mit 1<t<p auch Teiler von n wäre und daher in T liegt, im Widerspruch zur Minimaleigenschaft von p... Wink

25.06.2012, 07:04

Deborah

Auf diesen Beitrag antworten »

1) Du musstest die Aufgabe ja nach dem Beweis von Euklid machen. Wenn dies nicht der Fall wäre, könntest du den Primzahlsatz von Dirichlet verwenden:

Sind a und d teilerfremd, so gibt es in der arithmetischen Folge a + k*d unendlich viele Primzahlen.

a=3 d=4 p=3+k*4

2) @Darthidus
Das ist der Beweis, dass es unendlich viele Primzahlen gibt, aber nicht, dass es unendlich viele Primzahen der Form 4n+3 gibt.

Dieselbe Beweisidee funktioniert hier, aber nur, weil wir die Folge 4n+3 haben. Bei der Folge 6n+5 käme man damit nicht zum Ziel.

Nehmen wir an, es gibt nur endlich viele. Wenn ich alle multipliziere, erhalte ich - je nachdem, ob die Anzahl gerade oder ungerade ist, eine Zahl der Form 4m+1 oder 4m+3.
Multipliziert man noch mit 2, hat man 4r+2. Addiert man 1, ergibt das t=4r+3, von dem zumindest ein Primfaktor noch nicht vorgekommen ist.
t kann nicht durch Multiplikation nur von Primfaktoren der Form 4n+1 zustande gekommen sein.

25.06.2012, 08:46

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Deborah
1) Du musstest die Aufgabe ja nach dem Beweis von Euklid machen. Wenn dies nicht der Fall wäre, könntest du den Primzahlsatz von Dirichlet verwenden:

Sind a und d teilerfremd, so gibt es in der arithmetischen Folge a + k*d unendlich viele Primzahlen.

a=3 d=4 p=3+k*4

Wen hast du da genau angesprochen? Da wir aber alle die ganze Zeit über den Originalbeweis von Euklid reden und was man dafür braucht, sehe ich aber ohnehin keinen Sinn dahinter... verwirrt

Zitat:

Original von Deborah
2) @Darthidus
Das ist der Beweis, dass es unendlich viele Primzahlen gibt, aber nicht, dass es unendlich viele Primzahen der Form 4n+3 gibt.

So wie ich das sehe, bezog sich die Frage von Darthidus nicht mehr auf das Originalproblem von Arizona aus dem Jahr 2009(!), sondern wirklich auf Euklid's Beweis... geschockt

Übrigens geht der Beweis für die Primzahlen der Form 4k+3 etwas eleganter (und auch näher zu Euklid's Beweis!), indem man annimmt, es gäbe nur endlich viel Primzahlen $\begin{eqnarray*} p_1,p_2,\ldots,p_s \end{eqnarray*}$ dieser Form und dann damit $\begin{eqnarray*} N=4p_1p_2\cdots p_s-1 \end{eqnarray*}$ bildet...Danach geht es weiter wie gewohnt... Augenzwinkern

25.06.2012, 17:48

Deborah

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic

Übrigens geht der Beweis für die Primzahlen der Form 4k+3 etwas eleganter (und auch näher zu Euklid's Beweis!), indem man annimmt, es gäbe nur endlich viel Primzahlen $\begin{eqnarray*} p_1,p_2,\ldots,p_s \end{eqnarray*}$ dieser Form und dann damit $\begin{eqnarray*} N=4p_1p_2\cdots p_s-1 \end{eqnarray*}$ bildet...Danach geht es weiter wie gewohnt... Augenzwinkern

Naja, sehr unterscheidet sich das nicht von meinem Vorschlag das Produkt aller (endlich vielen) Primzahlen der Form 4n+3 zu multiplizieren, danach mit 2 zu multiplizieren und dann noch 1 zu addieren.
$\begin{eqnarray*} N=2p_1p_2\cdots p_s+1 \end{eqnarray*}$ , denn dieses N ist kongruent 3mod(4), wie man ja sofort sieht.

Genauso wie bei dir. Augenzwinkern

Warum findest du die Multipliktion mit 4 eleganter?

25.06.2012, 18:47

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von Deborah
Warum findest du die Multipliktion mit 4 eleganter?

Es ist halt ein typisches ad hoc-Argument und wenn du z.B. zeigen wolltest, dass es unendlich viele Primzahlen der Form 6k+5 gibt, müßtest du dir was Neues ausdenken, während mein Argument mutatis mutandis noch immer funktioniert...

Aber es ist vermutlich wirklich nur Geschmackssache und ich bin dir ja auch nicht böse, wenn du anderer Meinung bist... Augenzwinkern

Neue Frage »

Antworten »

Unendlich viele Primzahlen - Beweis nach Euklid

Verwandte Themen