Primzahlen modulo 6 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 06:55 Mo 31.10.2011 | | Autor: | Nisse |
| Aufgabe | | Beweise oder widerlege: Es gibt unendlich viele Primzahlen der Form $6n+5$. |
Moin,
hier ist meine nächste Zahlentheorie-Aufgabe. Ich forme als erstes die Aufgabenstellung um:
p hat Form $6n+5 [mm] \quad\Leftrightarrow\quad [/mm] p [mm] \equiv [/mm] 5 [mm] \mod [/mm] 6 [mm] \quad\Leftrightarrow\quad [/mm] p [mm] \equiv [/mm] -1 [mm] \mod [/mm] 6$.
Dann kann ich mir die Reste modulo 6 anschauen und auf Primkandidaten untersuchen (p>3):
$p [mm] \equiv [/mm] 0 [mm] \mod [/mm] 6$ 2 & 3 teilen, nicht prim
$p [mm] \equiv [/mm] 1 [mm] \mod [/mm] 6$ eventuell prim
$p [mm] \equiv [/mm] 2 [mm] \mod [/mm] 6$ 2 teilt, nicht prim
$p [mm] \equiv [/mm] 3 [mm] \mod [/mm] 6$ 3 teilt, nicht prim
$p [mm] \equiv [/mm] 4 [mm] \mod [/mm] 6$ 2 teilt, nicht prim
$p [mm] \equiv [/mm] 5 [mm] \mod [/mm] 6$ eventuell prim
Es ergibt sich also, dass für Primzahlen [mm] $p\in\IP, \quad [/mm] p>3$ gilt: $p [mm] \equiv \pm [/mm] 1 [mm] \mod [/mm] 6$
Und dann verliessen sie ihn... Ich habe noch im Hinterkopf, dass wir damals in der ZT-Vorlesung für beide Fälle nachgewiesen haben, dass es unendlich viele Primzahlen dieser Form gibt, aber ich habe keine Beweisidee (außer einer: einem Widerspruchs-Beweis nach dem Satz von Euklid, aber ich schaffe es nicht, eine neue Zahl zu konstruieren, die sowohl prim ist, als auch den richtigen Rest modulo 6 hat).
|
|
| |
|
Hallo,
Angenommen es gibt nur endlich viele Primzahlen der Form $6n+5$. Diese seien : [mm] $p_{1},…,p_{k}$. [/mm] Dann gibt es auch $K = 6 [mm] (p_{1}\cdot [/mm] ... [mm] \cdot p_{k} [/mm] -1) + 5 = [mm] 6p_{1}\cdot [/mm] ... [mm] \cdot p_{k} [/mm] -1$. Damit gilt $K [mm] \equiv [/mm] 5 [mm] \mod [/mm] 6 $. Es gibt ein x mit $x|K$ so dass $x [mm] \equiv 5\mod [/mm] 6$ weil für $a [mm] \equiv 1\mod [/mm] 6$ und $b [mm] \equiv [/mm] 1 [mm] \mod [/mm] 6 [mm] \Rightarrow [/mm] ab [mm] \equiv [/mm] 1 [mm] \mod [/mm] 6$. Dieses x teilt K+1 und K. Dies führt auf x|1, Widerspruch.
Gruss
kushkush
|
|
|
| |
|
Hallo Nisse,
man kann unendlich viele andere Zahlen entwerfen als die von kushkush und dabei trotzdem das Prinzip von Euklids Beweis nutzen.
z.B. so -
Angenommen es gibt nur endlich viele Primzahlen der Form $ 6n+5 $. Diese seien : $ [mm] p_{1},…,p_{k} [/mm] $.
Für k=2j sei [mm] K=\left(\produkt_{i=1}^{k}p_i\right)-2
[/mm]
Für k=2j+1 sei [mm] K=5*\left(\produkt_{i=1}^{k}p_i\right)-2
[/mm]
Damit gilt $ K [mm] \equiv [/mm] 5 [mm] \mod [/mm] 6 $. Es gibt ein x mit $ x|K $ so dass $ x [mm] \equiv 5\mod [/mm] 6 $ weil für $ a [mm] \equiv 1\mod [/mm] 6 $ und $ b [mm] \equiv [/mm] 1 [mm] \mod [/mm] 6 [mm] \Rightarrow [/mm] ab [mm] \equiv [/mm] 1 [mm] \mod [/mm] 6 $. Dieses x teilt K+1 und K. Dies führt auf x|1, Widerspruch.
Grüße (auch an kushkush, von dem ich oben fast alles geklaut habe),
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:09 Mo 31.10.2011 | | Autor: | Nisse |
> z.B. so -
> Angenommen es gibt nur endlich viele Primzahlen der Form
> [mm]6n+5 [/mm]. Diese seien : [mm]p_{1},…,p_{k} [/mm].
> Für k=2j sei [mm]K=\left(\produkt_{i=1}^{k}p_i\right)-2[/mm]
> Für k=2j+1 sei [mm]K=5*\left(\produkt_{i=1}^{k}p_i\right)-2[/mm]
>
> Damit gilt [mm]K \equiv 5 \mod 6 [/mm]. Es gibt ein x mit [mm]x|K[/mm] so
> dass [mm]x \equiv 5\mod 6[/mm] weil für [mm]a \equiv 1\mod 6[/mm] und [mm]b \equiv 1 \mod 6 \Rightarrow ab \equiv 1 \mod 6 [/mm].
> Dieses x teilt K+1 und K. Dies führt auf x|1,
> Widerspruch.
Vielen Dank euch beiden!
Ich hake noch ein wenig bei der Begründung für die Existenz von x. Ich probiere es mal so:
Sei [mm] $x_1 x_2 [/mm] ... [mm] x_r$ [/mm] die Primfaktorzerlegung von K. Wegen $K [mm] \equiv [/mm] -1 [mm] \bmod [/mm] 6$ und Rechenregeln in $ [mm] \IZ [/mm] / [mm] 6\IZ$ [/mm] besteht diese PFZ aus einer ungeraden Anzahl von [mm] $x_i \equiv [/mm] -1 [mm] \bmod [/mm] 6$ und dem Rest [mm] $x_j \equiv [/mm] 1 [mm] \bmod [/mm] 6$. Es gibt also mindestens ein [mm] $x_i$ [/mm] mit [mm] $x_i \equiv [/mm] -1 [mm] \bmod [/mm] 6$.
Für dieses [mm] $x_i$ [/mm] gilt: [mm] $x_i \mid [/mm] K$ (da [mm] x_i [/mm] Primfaktorvon K) und [mm] $x_i \mid [/mm] K+1$, also auch [mm] $x_i \mid [/mm] K+1-K = 1$. Dies ist ein Widerspruch, da $x [mm] \mid [/mm] 1$ nur von $x= [mm] \pm [/mm] 1$ gelöst wird, aber [mm] $x_i [/mm] > 0$ und [mm] $x_i \equiv [/mm] 5 [mm] \bmod [/mm] 6$ gilt.
Okay soweit, aber was ich noch nicht verstanden habe ist, warum [mm] $x_i \mid [/mm] K+1$ gelten sollte.
|
|
|
| |
|
Hallo Nisse,
Du hast vollkommen Recht. Das ist nicht sauber formuliert, aber der Gedanke ist richtig. Für meinen Entwurf muss man da sogar noch mehr abwandeln.
> > z.B. so -
> > Angenommen es gibt nur endlich viele Primzahlen der
> Form
> > [mm]6n+5 [/mm]. Diese seien : [mm]p_{1},…,p_{k} [/mm].
> > Für k=2j sei [mm]K=\left(\produkt_{i=1}^{k}p_i\right)-2[/mm]
> > Für k=2j+1 sei
> [mm]K=5*\left(\produkt_{i=1}^{k}p_i\right)-2[/mm]
> >
> > Damit gilt [mm]K \equiv 5 \mod 6 [/mm]. Es gibt ein x mit [mm]x|K[/mm] so
> > dass [mm]x \equiv 5\mod 6[/mm] weil für [mm]a \equiv 1\mod 6[/mm] und [mm]b \equiv 1 \mod 6 \Rightarrow ab \equiv 1 \mod 6 [/mm].
> > Dieses x teilt K+1 und K. Dies führt auf x|1,
> > Widerspruch.
>
> Vielen Dank euch beiden!
>
> Ich hake noch ein wenig bei der Begründung für die
> Existenz von x. Ich probiere es mal so:
>
> Sei [mm]x_1 x_2 ... x_r[/mm] die Primfaktorzerlegung von K. Wegen [mm]K \equiv -1 \bmod 6[/mm]
> und Rechenregeln in [mm]\IZ / 6\IZ[/mm] besteht diese PFZ aus einer
> ungeraden Anzahl von [mm]x_i \equiv -1 \bmod 6[/mm] und dem Rest [mm]x_j \equiv 1 \bmod 6[/mm].
> Es gibt also mindestens ein [mm]x_i[/mm] mit [mm]x_i \equiv -1 \bmod 6[/mm].
![[ok]](/images/smileys/ok.gif "[ok]")
> Für dieses [mm]x_i[/mm] gilt: [mm]x_i \mid K[/mm] (da [mm]x_i[/mm] Primfaktorvon K)
> und [mm]x_i \mid K+1[/mm], also auch [mm]x_i \mid K+1-K = 1[/mm]. Dies ist
> ein Widerspruch, da [mm]x \mid 1[/mm] nur von [mm]x= \pm 1[/mm] gelöst wird,
> aber [mm]x_i > 0[/mm] und [mm]x_i \equiv 5 \bmod 6[/mm] gilt.
Umgekehrt wärs richtig: Jeder Primteiler [mm] x_i [/mm] von K, der [mm] x_i\equiv 5\mod{6} [/mm] erfüllt, muss per definitionem in der vollständigen Liste aller Primzahlen der Form 6m-1 enthalten sein und daher auch K+1 teilen.
> Okay soweit, aber was ich noch nicht verstanden habe ist,
> warum [mm]x_i \mid K+1[/mm] gelten sollte.
In meiner Fassung geht es minimal anders.
Verallgemeinert wäre die ja:
[mm] K=\produkt_{i=1}^{k}p_i^{\alpha_i}-2 [/mm] mit [mm] \alpha_i\in\IN\setminus\{0\} [/mm] und [mm] \summe_{i=1}^{k}\alpha_i=2s
[/mm]
Dann ist [mm] K\equiv 5\mod{6}.
[/mm]
Jeder Primteiler [mm] x_i [/mm] von K, der die Form 6m-1 hat, muss auch K+2 teilen (wegen der Vollständigkeit der Auflistung), also [mm] 2|x_i. [/mm] Widerspruch.
Grüße
reverend
|
|
|
|
