Unendlich viele Primzahlen. < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Sei [mm] \phi_{n} [/mm] das n-te Kreisteilungspolynom. Sei [mm] P(\phi_{n}) [/mm] die Menge aller Primzahlen p mit [mm] p\nmid [/mm] n und so dass [mm] \phi_{n} [/mm] mod [mm] p\mathbb{Z}[X] [/mm] eine Nullstelle in [mm] \mathbb{Z}/p\mathbb{Z} [/mm] besitzt. Zeigen Sie, dass [mm] P(\phi_{n}) [/mm] eine unendliche Menge ist. Folgern Sie, dass es unendlich viele Primzahlen p gibt mit [mm] p\equiv1modn. [/mm] |
Hallo,
ich habe einige Sachen vorliegen, die mir unzureichend sind.
Seien [mm] p_{1},...,p_{r}\in P(\phi_{n}). [/mm] Wähle eine natürliche Zahl m, so dass [mm] \phi_{n}(mp_{1}\cdot\cdot\cdot p_{r})>1. [/mm] Dann gibt es eine Primzahl q mit [mm] q|\phi_{n}(mp_{1}\cdot\cdot\cdot p_{r}). [/mm] Also gilt [mm] \phi_{n}(mp_{1}\cdot\cdot\cdot p_{r})\equiv0 [/mm] mod q. An dieser Stelle wird bereits gefolgert (nachdem man über das Kreisteilungspolynom noch gezeigt hat, dass [mm] q\neq p_{i} [/mm] ist für alle i=1,...,r), dass [mm] q\in P(\phi_{n}) [/mm] ist. Aber es ist doch noch nirgends gezeigt worden, dass [mm] q\nmid [/mm] n gilt. Oder folgt das aus irgendeinem der Schritte?
Dann wählt man irgendein [mm] p\in P(\phi_{n}). [/mm] Nach Voraussetzung gibt es dann ein k mit [mm] \phi_{n}(k)\equiv0 [/mm] mod p. Aus einem Lemma weiß man, dass dann die ord(k)=n ist in [mm] (\mathbb{Z}/p\mathbb{Z})*. [/mm] Das kann ich akzeptieren. Jetzt teilt die Ordnung aller Elemente in [mm] (\mathbb{Z}/p\mathbb{Z})* [/mm] die Gruppenordnung selbst, was ja p-1 ist. Nun sagt man auf einmal, dass dann n|p-1, was ja bedeuten würde, dass k in der Gruppe [mm] (\mathbb{Z}/p\mathbb{Z})* [/mm] liegen müsste. Aber warum sollte das denn nun gelten? Naja wenn das dann wirklich gilt, ist mir auch klar dass sofort [mm] p\equiv1 [/mm] mod n folgt.
Grüße
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:49 Do 23.09.2010 | | Autor: | felixf |
Moin!
> Sei [mm]\phi_{n}[/mm] das n-te Kreisteilungspolynom. Sei [mm]P(\phi_{n})[/mm]
> die Menge aller Primzahlen p mit [mm]p\nmid[/mm] n und so dass
> [mm]\phi_{n}[/mm] mod [mm]p\mathbb{Z}[X][/mm] eine Nullstelle in
> [mm]\mathbb{Z}/p\mathbb{Z}[/mm] besitzt. Zeigen Sie, dass
> [mm]P(\phi_{n})[/mm] eine unendliche Menge ist. Folgern Sie, dass es
> unendlich viele Primzahlen p gibt mit [mm]p\equiv1modn.[/mm]
> Hallo,
>
> ich habe einige Sachen vorliegen, die mir unzureichend
> sind.
>
> Seien [mm]p_{1},...,p_{r}\in P(\phi_{n}).[/mm] Wähle eine
> natürliche Zahl m, so dass [mm]\phi_{n}(mp_{1}\cdot\cdot\cdot p_{r})>1.[/mm]
> Dann gibt es eine Primzahl q mit
> [mm]q|\phi_{n}(mp_{1}\cdot\cdot\cdot p_{r}).[/mm] Also gilt
> [mm]\phi_{n}(mp_{1}\cdot\cdot\cdot p_{r})\equiv0[/mm] mod q. An
> dieser Stelle wird bereits gefolgert (nachdem man über das
> Kreisteilungspolynom noch gezeigt hat, dass [mm]q\neq p_{i}[/mm] ist
> für alle i=1,...,r), dass [mm]q\in P(\phi_{n})[/mm] ist. Aber es
> ist doch noch nirgends gezeigt worden, dass [mm]q\nmid[/mm] n gilt.
> Oder folgt das aus irgendeinem der Schritte?
Das wurde auch nirgendwo gezeigt, und es ist auch falsch. Angenommen, $r = 0$ und $n = 3$. Dann ist [mm] $\phi_n(x) [/mm] = [mm] x^2 [/mm] + x + 1$, und mit $m = 4$ ist [mm] $\phi_n(m) [/mm] = 21$. Die Primzahl $q = 3$ teilt [mm] $\phi_n(m)$, [/mm] ist jedoch nicht teilerfremd zu $n$!
Der Beweis ist so also nicht vollstaendig.
> Dann wählt man irgendein [mm]p\in P(\phi_{n}).[/mm] Nach
> Voraussetzung gibt es dann ein k mit [mm]\phi_{n}(k)\equiv0[/mm] mod
> p. Aus einem Lemma weiß man, dass dann die ord(k)=n ist in
> [mm](\mathbb{Z}/p\mathbb{Z})*.[/mm] Das kann ich akzeptieren. Jetzt
> teilt die Ordnung aller Elemente in
> [mm](\mathbb{Z}/p\mathbb{Z})*[/mm] die Gruppenordnung selbst, was ja
> p-1 ist. Nun sagt man auf einmal, dass dann n|p-1, was ja
> bedeuten würde, dass k in der Gruppe
> [mm](\mathbb{Z}/p\mathbb{Z})*[/mm] liegen müsste.
Nun, wenn es da nicht drinnen liegt, macht es doch gar keinen Sinn von der Ordnung zu sprechen! Ordnung gibt's nur fuer invertierbare Elemente!
> Aber warum sollte
> das denn nun gelten? Naja wenn das dann wirklich gilt, ist
> mir auch klar dass sofort [mm]p\equiv1[/mm] mod n folgt.
Angenommen, [mm] $\phi_n(k)$ [/mm] ist durch $q$ teilbar und $k$ ebenfalls. Da [mm] $\phi_n$ [/mm] ein Teiler von [mm] $x^n [/mm] - 1$ ist, muss [mm] $\phi_n(k)$ [/mm] ein Teiler von [mm] $k^n [/mm] - 1$ sein, womit es ein $z [mm] \in \IZ$ [/mm] gibt mit [mm] $\phi_n(k) \cdot [/mm] z = [mm] k^n [/mm] - 1$. Modulo $q$ steht dann dort aber $0 [mm] \equiv [/mm] 1 [mm] \pmod{q}$, [/mm] ein Widerspruch. Also kann $k$ nicht durch $q$ teilbar sein, womit $q$ in [mm] $(\IZ/q\IZ)^\ast$ [/mm] liegt.
LG Felix
|
|
|
| |
|
Hallo,
> Moin!
>
> > Sei [mm]\phi_{n}[/mm] das n-te Kreisteilungspolynom. Sei [mm]P(\phi_{n})[/mm]
> > die Menge aller Primzahlen p mit [mm]p\nmid[/mm] n und so dass
> > [mm]\phi_{n}[/mm] mod [mm]p\mathbb{Z}[X][/mm] eine Nullstelle in
> > [mm]\mathbb{Z}/p\mathbb{Z}[/mm] besitzt. Zeigen Sie, dass
> > [mm]P(\phi_{n})[/mm] eine unendliche Menge ist. Folgern Sie, dass es
> > unendlich viele Primzahlen p gibt mit [mm]p\equiv1modn.[/mm]
> > Hallo,
> >
> > ich habe einige Sachen vorliegen, die mir unzureichend
> > sind.
> >
> > Seien [mm]p_{1},...,p_{r}\in P(\phi_{n}).[/mm] Wähle eine
> > natürliche Zahl m, so dass [mm]\phi_{n}(mp_{1}\cdot\cdot\cdot p_{r})>1.[/mm]
> > Dann gibt es eine Primzahl q mit
> > [mm]q|\phi_{n}(mp_{1}\cdot\cdot\cdot p_{r}).[/mm] Also gilt
> > [mm]\phi_{n}(mp_{1}\cdot\cdot\cdot p_{r})\equiv0[/mm] mod q. An
> > dieser Stelle wird bereits gefolgert (nachdem man über das
> > Kreisteilungspolynom noch gezeigt hat, dass [mm]q\neq p_{i}[/mm] ist
> > für alle i=1,...,r), dass [mm]q\in P(\phi_{n})[/mm] ist. Aber es
> > ist doch noch nirgends gezeigt worden, dass [mm]q\nmid[/mm] n gilt.
> > Oder folgt das aus irgendeinem der Schritte?
>
> Das wurde auch nirgendwo gezeigt, und es ist auch falsch.
> Angenommen, [mm]r = 0[/mm] und [mm]n = 3[/mm]. Dann ist [mm]\phi_n(x) = x^2 + x + 1[/mm],
> und mit [mm]m = 4[/mm] ist [mm]\phi_n(m) = 21[/mm]. Die Primzahl [mm]q = 3[/mm] teilt
> [mm]\phi_n(m)[/mm], ist jedoch nicht teilerfremd zu [mm]n[/mm]!
>
> Der Beweis ist so also nicht vollstaendig.
>
> > Dann wählt man irgendein [mm]p\in P(\phi_{n}).[/mm] Nach
> > Voraussetzung gibt es dann ein k mit [mm]\phi_{n}(k)\equiv0[/mm] mod
> > p. Aus einem Lemma weiß man, dass dann die ord(k)=n ist in
> > [mm](\mathbb{Z}/p\mathbb{Z})*.[/mm] Das kann ich akzeptieren. Jetzt
> > teilt die Ordnung aller Elemente in
> > [mm](\mathbb{Z}/p\mathbb{Z})*[/mm] die Gruppenordnung selbst, was ja
> > p-1 ist. Nun sagt man auf einmal, dass dann n|p-1, was ja
> > bedeuten würde, dass k in der Gruppe
> > [mm](\mathbb{Z}/p\mathbb{Z})*[/mm] liegen müsste.
>
> Nun, wenn es da nicht drinnen liegt, macht es doch gar
> keinen Sinn von der Ordnung zu sprechen! Ordnung gibt's nur
> fuer invertierbare Elemente!
>
> > Aber warum sollte
> > das denn nun gelten? Naja wenn das dann wirklich gilt, ist
> > mir auch klar dass sofort [mm]p\equiv1[/mm] mod n folgt.
>
> Angenommen, [mm]\phi_n(k)[/mm] ist durch [mm]q[/mm] teilbar und [mm]k[/mm] ebenfalls.
> Da [mm]\phi_n[/mm] ein Teiler von [mm]x^n - 1[/mm] ist, muss [mm]\phi_n(k)[/mm] ein
> Teiler von [mm]k^n - 1[/mm] sein, womit es ein [mm]z \in \IZ[/mm] gibt mit
> [mm]\phi_n(k) \cdot z = k^n - 1[/mm]. Modulo [mm]q[/mm] steht dann dort aber
> [mm]0 \equiv 1 \pmod{q}[/mm], ein Widerspruch. Also kann [mm]k[/mm] nicht
> durch [mm]q[/mm] teilbar sein, womit [mm]q[/mm] in [mm](\IZ/q\IZ)^\ast[/mm] liegt.
>
du meinst [mm]k[/mm] in [mm](\IZ/q\IZ)^\ast[/mm]. Naja gut dann bin ich mit der Folgerung einverstanden. Aber der Teil, dass die Menge unendlich ist, fehlt noch.
Als Hinweis stand im Prinzip genau die beschriebene Vorgehensweise da: Man wählt sich das m, sodass [mm] \phi(mp_1\cdot\cdot\cdot p_r)>1 [/mm] ist. Dann besitzt das einen Primteiler p. Das ist klar.
Nun muss doch aber irgendwie das Ganze so konstruierbar sein, dass
p n nicht teilt. Kann man p irgendwie so wählen, dass es größer n ist? Dann müsste man das m entsprechend so wählen, dass [mm] \phi(mp_1\cdot\cdot\cdot p_r) [/mm] größer ist, als die Primzahl, die größer n ist und zu n den geringsten Abstand hat. Das kling komisch und ich glaube nicht, dass man es überhaupt so machen kann, aber rein theoretisch kann ich mein m auf jeden Fall so wählen, dass [mm] \phi(mp_1\cdot\cdot\cdot p_r)>n [/mm] ist, was aber noch nicht reicht.
Ich weiß nicht, wie man die Unendlichkeit zeigen kann.
> LG Felix
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:27 Do 23.09.2010 | | Autor: | felixf |
Moin!
> > > Sei [mm]\phi_{n}[/mm] das n-te Kreisteilungspolynom. Sei [mm]P(\phi_{n})[/mm]
> > > die Menge aller Primzahlen p mit [mm]p\nmid[/mm] n und so dass
> > > [mm]\phi_{n}[/mm] mod [mm]p\mathbb{Z}[X][/mm] eine Nullstelle in
> > > [mm]\mathbb{Z}/p\mathbb{Z}[/mm] besitzt. Zeigen Sie, dass
> > > [mm]P(\phi_{n})[/mm] eine unendliche Menge ist. Folgern Sie, dass es
> > > unendlich viele Primzahlen p gibt mit [mm]p\equiv1modn.[/mm]
> > > Hallo,
> > >
> > > ich habe einige Sachen vorliegen, die mir unzureichend
> > > sind.
> > >
> > > Seien [mm]p_{1},...,p_{r}\in P(\phi_{n}).[/mm] Wähle eine
> > > natürliche Zahl m, so dass [mm]\phi_{n}(mp_{1}\cdot\cdot\cdot p_{r})>1.[/mm]
> > > Dann gibt es eine Primzahl q mit
> > > [mm]q|\phi_{n}(mp_{1}\cdot\cdot\cdot p_{r}).[/mm] Also gilt
> > > [mm]\phi_{n}(mp_{1}\cdot\cdot\cdot p_{r})\equiv0[/mm] mod q. An
> > > dieser Stelle wird bereits gefolgert (nachdem man über das
> > > Kreisteilungspolynom noch gezeigt hat, dass [mm]q\neq p_{i}[/mm] ist
> > > für alle i=1,...,r), dass [mm]q\in P(\phi_{n})[/mm] ist. Aber es
> > > ist doch noch nirgends gezeigt worden, dass [mm]q\nmid[/mm] n gilt.
> > > Oder folgt das aus irgendeinem der Schritte?
> >
> > Das wurde auch nirgendwo gezeigt, und es ist auch falsch.
> > Angenommen, [mm]r = 0[/mm] und [mm]n = 3[/mm]. Dann ist [mm]\phi_n(x) = x^2 + x + 1[/mm],
> > und mit [mm]m = 4[/mm] ist [mm]\phi_n(m) = 21[/mm]. Die Primzahl [mm]q = 3[/mm] teilt
> > [mm]\phi_n(m)[/mm], ist jedoch nicht teilerfremd zu [mm]n[/mm]!
> >
> > Der Beweis ist so also nicht vollstaendig.
> >
> > > Dann wählt man irgendein [mm]p\in P(\phi_{n}).[/mm] Nach
> > > Voraussetzung gibt es dann ein k mit [mm]\phi_{n}(k)\equiv0[/mm] mod
> > > p. Aus einem Lemma weiß man, dass dann die ord(k)=n ist in
> > > [mm](\mathbb{Z}/p\mathbb{Z})*.[/mm] Das kann ich akzeptieren. Jetzt
> > > teilt die Ordnung aller Elemente in
> > > [mm](\mathbb{Z}/p\mathbb{Z})*[/mm] die Gruppenordnung selbst, was ja
> > > p-1 ist. Nun sagt man auf einmal, dass dann n|p-1, was ja
> > > bedeuten würde, dass k in der Gruppe
> > > [mm](\mathbb{Z}/p\mathbb{Z})*[/mm] liegen müsste.
> >
> > Nun, wenn es da nicht drinnen liegt, macht es doch gar
> > keinen Sinn von der Ordnung zu sprechen! Ordnung gibt's nur
> > fuer invertierbare Elemente!
> >
> > > Aber warum sollte
> > > das denn nun gelten? Naja wenn das dann wirklich gilt, ist
> > > mir auch klar dass sofort [mm]p\equiv1[/mm] mod n folgt.
> >
> > Angenommen, [mm]\phi_n(k)[/mm] ist durch [mm]q[/mm] teilbar und [mm]k[/mm] ebenfalls.
> > Da [mm]\phi_n[/mm] ein Teiler von [mm]x^n - 1[/mm] ist, muss [mm]\phi_n(k)[/mm] ein
> > Teiler von [mm]k^n - 1[/mm] sein, womit es ein [mm]z \in \IZ[/mm] gibt mit
> > [mm]\phi_n(k) \cdot z = k^n - 1[/mm]. Modulo [mm]q[/mm] steht dann dort aber
> > [mm]0 \equiv 1 \pmod{q}[/mm], ein Widerspruch. Also kann [mm]k[/mm] nicht
> > durch [mm]q[/mm] teilbar sein, womit [mm]q[/mm] in [mm](\IZ/q\IZ)^\ast[/mm] liegt.
>
> du meinst [mm]k[/mm] in [mm](\IZ/q\IZ)^\ast[/mm].
Ja.
> Naja gut dann bin ich mit
> der Folgerung einverstanden. Aber der Teil, dass die Menge
> unendlich ist, fehlt noch.
Genau.
> Als Hinweis stand im Prinzip genau die beschriebene
> Vorgehensweise da: Man wählt sich das m, sodass
> [mm]\phi(mp_1\cdot\cdot\cdot p_r)>1[/mm] ist. Dann besitzt das einen
> Primteiler p. Das ist klar.
> Nun muss doch aber irgendwie das Ganze so konstruierbar
> sein, dass
> p n nicht teilt. Kann man p irgendwie so wählen, dass es
> größer n ist? Dann müsste man das m entsprechend so
> wählen, dass [mm]\phi(mp_1\cdot\cdot\cdot p_r)[/mm] größer ist,
> als die Primzahl, die größer n ist und zu n den
> geringsten Abstand hat. Das kling komisch und ich glaube
> nicht, dass man es überhaupt so machen kann, aber rein
> theoretisch kann ich mein m auf jeden Fall so wählen, dass
> [mm]\phi(mp_1\cdot\cdot\cdot p_r)>n[/mm] ist, was aber noch nicht
> reicht.
Du hattest doch schon gezeigt, dass $p$ keins der [mm] $p_i$ [/mm] sein kann. Wenn du $m$ als Vielfaches von $n$ waehlst, kann somit $p$ auch kein Primteiler von $m$ und somit auch keiner von $n$ sein.
Dann bekommst du also tatsaechlich ein Element von [mm] $P(\phi_n)$.
[/mm]
LG Felix
|
|
|
|
