quadratischer Rest modulo 4 < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei n eine natürliche Zahl und p ein Primteiler p>2 von [mm] n^2+1. [/mm] Zeigen Sie:
(i) [mm] p\equiv [/mm] 1 mod 4,
(ii) Mit Verwendung von (i): Es gibt unendlich viele Primzahlen der Form 4n+1, [mm] n\in \mathbb{N}. [/mm] |
Hallo,
ich hab mir schon ein paar Sachen überlegt:
Zu (i):
Sei also [mm] n\in\mathbb{N} [/mm] und p>2 Primteiler von [mm] n^{2}+1. [/mm] Dann gilt: [mm] p|n^{2}+1\Rightarrow n^{2}+1\equiv0\,\,\mbox{mod }p\Rightarrow n^{2}\equiv-1\,\,\mbox{mod }p.
[/mm]
Weiterhin ist ziemlich klar, dass [mm] n^{2}\equiv\begin{cases}
0\,\,\mbox{mod }4 & \mbox{falls }n\,\,\mbox{gerade}\\
1\,\,\mbox{mod }4 & \mbox{sonst}\end{cases}.
[/mm]
Jetzt fängts bei mir an falsch zu werden:
Ich mache eine Fallunterscheidung: n gerade: Dann gilt:
[mm] n^2\equiv [/mm] 0 mod 4 und [mm] n^2\equiv [/mm] -1 mod p, also folgt doch
4a+1=-1+pb mit natürlichen Zahlen a, b.
Daraus folgt pb=4a+1. Das sieht ja schon fast richtig aus, wenn b jetzt gleich 1 wäre. Aber ich kann doch aus [mm] n^2\equiv [/mm] -1 mod p nur schließen, dass gilt [mm] n^2=-1+pb [/mm] und nicht etwa direkt [mm] n^2=-1+p [/mm] oder?
Muss ich es anders machen?
Naja im ungeraden Fall verirre ich mich noch weiter, denn dann gilt: [mm] n^2\equiv [/mm] 1 mod 4, also [mm] 4a+1=pb-1\Rightarrow [/mm] pb=4a+2.
Weiter kann ich nichts sagen. Wie kann ich zu dem richtigen Ergebnis kommen?
Zu (ii):
Ich weiß nicht recht, wie ich argumentieren soll. Angenommen es gibt nur endlich viele Primzahlen etwa [mm] q_1 [/mm] bis [mm] q_t, [/mm] wobei [mm] q_t [/mm] die größte sei.
Dann muss ich ja irgendwie zu einem Widerspruch kommen. Bisher ist mir das noch nicht gelungen.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:17 Mo 28.12.2009 | | Autor: | felixf |
Hallo!
> Sei n eine natürliche Zahl und p ein Primteiler p>2 von
> [mm]n^2+1.[/mm] Zeigen Sie:
> (i) [mm]p\equiv[/mm] 1 mod 4,
> (ii) Mit Verwendung von (i): Es gibt unendlich viele
> Primzahlen der Form 4n+1, [mm]n\in \mathbb{N}.[/mm]
>
> Hallo,
>
> ich hab mir schon ein paar Sachen überlegt:
> Zu (i):
> Sei also [mm]n\in\mathbb{N}[/mm] und p>2 Primteiler von [mm]n^{2}+1.[/mm]
> Dann gilt: [mm]p|n^{2}+1\Rightarrow n^{2}+1\equiv0\,\,\mbox{mod }p\Rightarrow n^{2}\equiv-1\,\,\mbox{mod }p.[/mm]
Du hast gezeigt: die multiplikative Gruppe [mm] $(\IZ [/mm] / p [mm] \IZ)^\ast$ [/mm] hat ein Element der Ordnung 4. Was sagt das ueber die Ordnung aus?
> Weiterhin ist ziemlich klar, dass [mm]n^{2}\equiv\begin{cases}
0\,\,\mbox{mod }4 & \mbox{falls }n\,\,\mbox{gerade}\\
1\,\,\mbox{mod }4 & \mbox{sonst}\end{cases}.[/mm]
>
> Jetzt fängts bei mir an falsch zu werden:
> Ich mache eine Fallunterscheidung: n gerade: Dann gilt:
> [mm]n^2\equiv[/mm] 0 mod 4 und [mm]n^2\equiv[/mm] -1 mod p, also folgt doch
> 4a+1=-1+pb mit natürlichen Zahlen a, b.
Kann es sein dass du dich hier vertippt hast?
> Weiter kann ich nichts sagen. Wie kann ich zu dem richtigen
> Ergebnis kommen?
Mach's mal ueber Lagrange und Gruppen, wie oben 
> Zu (ii):
> Ich weiß nicht recht, wie ich argumentieren soll.
> Angenommen es gibt nur endlich viele Primzahlen etwa [mm]q_1[/mm]
> bis [mm]q_t,[/mm] wobei [mm]q_t[/mm] die größte sei.
> Dann muss ich ja irgendwie zu einem Widerspruch kommen.
> Bisher ist mir das noch nicht gelungen.
Oft macht man bei sowas folgendes: man multipliziert die Primzahlen zusammen und addiert 1. Dann bekommt man eine Zahl, die nicht durch die Primzahlen teilbar ist.
Kannst du etwas aehnliches probieren? Wenn etwa [mm] $q_i [/mm] = [mm] n_i^2 [/mm] + 1$ ist, kannst du dann [mm] $(\prod_{i=1}^t n_i)^2 [/mm] + 1$ anschauen? Ist dies durch ein [mm] $q_i$ [/mm] teilbar? (Ich hab's nicht nachgeprueft, aber es koennte so funktionieren.)
LG Felix
|
|
|
| |
|
> Hallo!
>
> > Sei n eine natürliche Zahl und p ein Primteiler p>2 von
> > [mm]n^2+1.[/mm] Zeigen Sie:
> > (i) [mm]p\equiv[/mm] 1 mod 4,
> > (ii) Mit Verwendung von (i): Es gibt unendlich viele
> > Primzahlen der Form 4n+1, [mm]n\in \mathbb{N}.[/mm]
> >
> > Hallo,
> >
> > ich hab mir schon ein paar Sachen überlegt:
> > Zu (i):
> > Sei also [mm]n\in\mathbb{N}[/mm] und p>2 Primteiler von [mm]n^{2}+1.[/mm]
> > Dann gilt: [mm]p|n^{2}+1\Rightarrow n^{2}+1\equiv0\,\,\mbox{mod }p\Rightarrow n^{2}\equiv-1\,\,\mbox{mod }p.[/mm]
>
> Du hast gezeigt: die multiplikative Gruppe [mm](\IZ / p \IZ)^\ast[/mm]
> hat ein Element der Ordnung 4. Was sagt das ueber die
> Ordnung aus?
Wieso habe ich hier ein Element der Ordnung 4? Ich weiß doch nur [mm] n^2+1\equiv [/mm] 0 mod p, aber das hat doch nicht die Ordnung 4?
Das kann ich noch nicht so ganz nachvollziehen.
Dann muss ja 4 die Kardinalität von [mm](\IZ / p \IZ)^\ast[/mm] teilen.
Diese sollte doch p-1 (ist es das denn auch? Die Null ist ja nicht mit drin) sein und damit habe ich es dann, richtig?
Zum zweiten Teil:
Das kann ich so nicht ganz machen glaube ich. Die Primzahlen sollen ja von der Form 4n+1 sein und nicht [mm] n^2+1. [/mm] Dann kann ich nicht [mm] q_i=n_i^{2}+1 [/mm] setzen. Was ich vielleicht sagen könnte ist, dass jedes [mm] q_i [/mm] Teiler von [mm] n_i^2+1 [/mm] sein soll. Dann ist [mm] q_i [/mm] eine Primzahl der Form 4n+1.
Wenn ich dann alle multipliziere komme ich aber nicht so recht weiter.
|
|
|
| |
|
Hallo T_sleeper,
> > > Sei n eine natürliche Zahl und p ein Primteiler p>2 von
> > > [mm]n^2+1.[/mm] Zeigen Sie:
> > > (i) [mm]p\equiv[/mm] 1 mod 4,
> > > (ii) Mit Verwendung von (i): Es gibt unendlich viele
> > > Primzahlen der Form 4n+1, [mm]n\in \mathbb{N}.[/mm]
> > >
> > > Hallo,
> > >
> > > ich hab mir schon ein paar Sachen überlegt:
> > > Zu (i):
> > > Sei also [mm]n\in\mathbb{N}[/mm] und p>2 Primteiler von
> [mm]n^{2}+1.[/mm]
> > > Dann gilt: [mm]p|n^{2}+1\Rightarrow n^{2}+1\equiv0\,\,\mbox{mod }p\Rightarrow n^{2}\equiv-1\,\,\mbox{mod }p.[/mm]
>
> >
> > Du hast gezeigt: die multiplikative Gruppe [mm](\IZ / p \IZ)^\ast[/mm]
> > hat ein Element der Ordnung 4. Was sagt das ueber die
> > Ordnung aus?
>
> Wieso habe ich hier ein Element der Ordnung 4? Ich weiß
> doch nur [mm]n^2+1\equiv[/mm] 0 mod p, aber das hat doch nicht die
> Ordnung 4?
> Das kann ich noch nicht so ganz nachvollziehen.
[mm] n^{2}\equiv-1\,\,\mbox{mod }p\quad \Rightarrow n^{4}\equiv+1\,\,\mbox{mod }p
[/mm]
> Dann muss ja 4 die Kardinalität von [mm](\IZ / p \IZ)^\ast[/mm]
> teilen.
> Diese sollte doch p-1 (ist es das denn auch? Die Null ist
> ja nicht mit drin) sein und damit habe ich es dann,
> richtig?
Ja, richtig. Fertig.
> Zum zweiten Teil:
> Das kann ich so nicht ganz machen glaube ich. Die
> Primzahlen sollen ja von der Form 4n+1 sein und nicht
> [mm]n^2+1.[/mm] Dann kann ich nicht [mm]q_i=n_i^{2}+1[/mm] setzen. Was ich
> vielleicht sagen könnte ist, dass jedes [mm]q_i[/mm] Teiler von
> [mm]n_i^2+1[/mm] sein soll. Dann ist [mm]q_i[/mm] eine Primzahl der Form
> 4n+1.
> Wenn ich dann alle multipliziere komme ich aber nicht so
> recht weiter.
Ich auch nicht, übrigens auch nicht mit der Idee von Felix.
Vielleicht kann man damit ansetzen, dass [mm] n^2+1 [/mm] nur dann selbst prim sein kann, wenn n im der Dezimaldarstellung auf 0,4 oder 6 endet. Natürlich ist das keine Garantie für Primalität: [mm] 30^2+1=17*53,\ 34^2+1=13*89,\ 44^2+1=13*149,\ 46^2=29*73,\ 50^2=41*61\ \cdots
[/mm]
Andere Frage: gibt es denn zu jedem [mm] p\equiv 1\mod{4} [/mm] mindestens ein n, so dass p Teiler von [mm] n^2+1 [/mm] ist? Hilft das weiter?
lg
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:13 Di 29.12.2009 | | Autor: | T_sleeper |
Danke, ich hab es hinbekommen.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 10:15 Di 29.12.2009 | | Autor: | reverend |
Moin,
> Danke, ich hab es hinbekommen.
Wie schön. Und wie? Der zweite Teil würde mich interessieren, vor allem, wie man ihn unter Verwendung des ersten beweist.
Zeig doch mal.
lg
rev
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:46 So 03.01.2010 | | Autor: | T_sleeper |
Erst einmal Entschuldigung für meine verspätete Reaktion, war die letzten Tage nicht so aktiv.
Ich werde den Beweis noch veröffentlichen, aber leider hat sich bisher bei mir noch eine kleine Ungereimtheit ergeben, die ich erstmal lösen muss, ich hoffe mal nicht, dass mir dadurch der ganze Beweis baden geht.
|
|
|
|
