Beweis unendlich Primzahlen mod 3

Aufrufe: 900     Aktiv: 03.12.2020 um 11:37
1

Hallo,

ich habe ein Problem mit folgender Aufgabe:

Mein Ansatz: Ich konstruiere die Zahl q1 mit der vorgegebenen Formel und zeige dann, dass ich unendlich viele q so konstruieren kann.

Allerdings weiß ich nicht genau, wie ich das machen soll und vor allem formulieren. Also ich wollte das induktiv beweisen. Es wäre schön, wenn mit jemand konkret sagen könnte, ob das richtig ist und wie man es dann formuliert.

 

Vielen Dank im Voraus und Viele Grüße

Diese Frage melden
gefragt

Punkte: 101

 
Kommentar schreiben
1 Antwort
1

Es geht wahrscheinlich auch mit Induktion, aber einfacher ist es per Widerspruch. Dann beginnst du so:

Angenommen, es gibt nur endlich viele Primzahlen \(p\) mit \(p\equiv 2\mod 3\). Seien diese \(p_1,\ldots,p_k\). Betrachte \(q=3p_1\cdots p_k-1\).

Jetzt musst du noch argumentieren, dass \(q\) durch keine der \(p_i\) teilbar ist und nicht alle Primfaktoren von \(q\) kongruent zu \(1\mod 3\) sein können. Dann entsteht ein Widerspruch dazu, dass jede Zahl eine Primfaktorzerlegung hat, also muss die Annahme falsch gewesen sein.

Probier mal, das noch selber fertig zu formulieren. Wenn du dabei noch Fragen hast, kannst du sie gern stellen.

Diese Antwort melden
geantwortet

Punkte: 11.27K

 
Es geht nicht per Induktion, sondern nur per Widerspruch, da Voraussetzung für eine Induktion eine induktive Menge ist, da wir jedoch beweisen sollen, dass es unendlich viele Primzahlen mit dieser Eigenschaft haben, dürfen wir keine induktive Menge annehmen.   ─   anonym0165f 01.12.2020 um 12:07
Hallo,

vielen Dank für die super Antwort!

Jetzt dürfte ich es hinkriegen, danke.

LG   ─   physikstudent(1.s) 01.12.2020 um 13:58
Hallo,

ich habe doch noch eine Frage:

also q ist durch kein p teilbar, weil wir am Ende -1 rechnen, richtig?
Ich verstehe das, was danach kommt nicht "und nicht alle Primfaktoren von q kongruent zu 1mod 3 sein können."
Was genau heißt das und wie führt mich das dann zum Widerspruch?

Eine nähere Erklärung dazu wäre super.

vielen Dank!   ─   physikstudent(1.s) 01.12.2020 um 14:17
Genau, \(q\) ist durch keines der \(p_i\) teilbar wegen dem \(-1\) am Ende.
Wir wissen, dass \(q\) eine Primfaktorzerlegung hat. Wir wollen zeigen, dass es einen Primfaktor von \(q\) gibt, der kongruent zu 2 modulo 3 ist, dann widerspricht das der Annahme, dass \(p_1,\ldots,p_k\) die einzigen Primzahlen dieser Form sind. Dieses Argument würde aber nicht funktionieren, Um das also zu zeigen, machen wir wieder einen Widerspruchsbeweis: Angenommen, alle Primfaktoren von \(q\) sind 0 oder 1 modulo 3. Was folgt dann für \(q\mod 3\)? Warum ist das ein Widerspruch?   ─   stal 01.12.2020 um 15:23
@anonym: Man könnte per vollständiger Induktion mit dem exakt gleichen Argument zeigen: \(\forall n\in\mathbb N\colon |\{p\ |\ p\text{ prim, }p\equiv2\mod 3\}|\geq n\). Daraus folgt auch die Behauptung.   ─   stal 01.12.2020 um 15:25
nein   ─   anonym0165f 01.12.2020 um 16:41
Warum nicht? Die Induktion läuft über \(\mathbb N\), die sind ja wohl induktiv geordnet.   ─   stal 01.12.2020 um 17:42
@stal,

also, ich versuche mal zu sagen, wie ich es verstanden habe:

zu zeigen ist, dass die Menge p unendlich ist.
Sei p endlich.
p teilt nicht q.
q ist zerlegbar in Primfaktoren.
Wenn wir jetzt zeigen, dass einer der Primfaktoren kongruent zu 2mod3 ist, haben wir eine neue Primzahl gefunden, die die Voraussetzung erfüllt, was der Annahme widerspricht, dass es nur endlich viele (nämlich p mit Laufindex i) gibt.
Sei dieser Primfaktoren 0 oder 1mod3. Dann wäre q entweder 0 oder nicht zerlegbar.
q kann nicht 0 sein, wenn man es mit der Formel:3* p1...-1 konstruiert, da p größer gleich 3 ist.
Wenn es 1mod3 ist, dann ist q selbst schon diese neue Primzahl und der Beweis endet hier.
Und wenn nichts von beidem zutrifft, dann ist der Primfaktor 2mod3.

Stimmt das so?

Vielen Dank für die Antwort!

LG   ─   physikstudent(1.s) 01.12.2020 um 18:54
Du hast schon die richtigen Ideen, aber es ist noch nicht richtig aufgeschrieben. Du verwendest den Buchstaben \(p\) in er ersten Zeile als Bezeichnung für eine Menge, ohne zu erklären, was \(p\) ist. Du könntest also so anfangen: "Sei \(P\) die Menge der Primzahlen, die kongruent zu \(2\) modulo \(3\) sind." Ich hab jetzt das P großgeschrieben, weil man normalerweise für Mengen Großbuchstaben verwendet. Die zweite Zeile ist ok, besser wäre noch "Angenommen, \(P\) wäre endlich." um gleich zu signalisieren, dass es ein Widerspruchsbeweis wird. In der nächsten Zeile verwendest du wieder den Buchstaben \(p\). Das kann jetzt sicher nicht mehr die Menge der Primzahlen sein, denn für eine Menge macht "teilen" keinen Sinn. Außerdem musst du noch \(q\) definieren, z.B. so: "Sei \(P=\{p_1,\ldots,p_k\}\) setze \(q:=3p_1p_2\cdots p_k-1\). Dann gilt für alle \(p\in P\), dass \(p\) nicht \(q\) teilt, da ... " für ... musst du noch eine Begründung einsetzen. (Betrachte z.B. \(q\mod p\). Die nächsten zwei Sätze sind gut. Statt "Sei dieser Primfaktoren" solltest du schreiben "Angenommen, alle Primfaktoren von \(q\) sind". Es ist immer wichtig klar zu machen, ob deine Aussage für alle oder für eine feste oder für eine beliebige Variable gelten soll.

Jetzt wird es bei dir ein bisschen wirr. Am besten unterscheidest du nun zwei Fälle: 1. Es gibt einen Primfaktor von \(q\) der kongruent zu 0 modulo 3 ist. Dann ist dieser Primfaktor 3. Betrachte \(q\mod 3\) um zu zeigen, dass 3 nicht \(q\) teilt. 2. Fall: Alle Primfaktoren von \(q\) sind kongruent zu 1 modulo 3. Dann ist ihr Produkt \(q\) kongruent zu \(1\cdot1\cdots1=1\mod 3\). Das kann auch nicht sein, denn \(q=2\mod 3\). Also kann dieser Fall auch nicht auftreten. Da beide Fälle zum Widerspruch führen, muss es einen Primfaktor von \(q\) geben, der nicht in \(P\) liegt und kongruent zu \(2\) modulo 3 ist, Widerspruch.

Versuch jetzt nochmal, das sauber aufzuschreiben.   ─   stal 02.12.2020 um 10:03
Hallo,

erst einmal vielen Dank für die ausführliche Antwort und die Zeit die du für mich aufwendest!

Bevor ich dir die neue Fassung schicke, habe ich noch 2 Fragen:

1. Wenn der Primfaktor 0mod3 = 0 ist, dann könnte er 3,6,9 usw. sein, aber auch 0 oder? Da könnte ich also noch einmal eine Fallunterscheidung machen, oder?

2. Wie schreibt man dieses P so fettgedruckt und groß/klein ? Ich habe in dem Code-Blatt nur Befehle für Formeln o.ä. gefunden.

Vielen Dank nochmal und LG.   ─   physikstudent(1.s) 02.12.2020 um 13:41
1. Aber ein Primfaktor ist prim, und von den Zahlen 0,3,6,9,.. ist nur 3 prim.
2. Du schreibst einfach das P als Formel, also \ (P\ ), nur ohne Leerzeichen zwischen den \ und den Klammern. Dann bekommt man \(P\). Leider sieht man in Kommentaren erst nach dem Abschicken, ob die Formatierung richtig geklappt hat.   ─   stal 03.12.2020 um 11:37

Kommentar schreiben