Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Status: |
(Frage) beantwortet | Datum: | 22:03 Mo 07.05.2012 | Autor: | teo |
Aufgabe | Zeigen Sie: Eine ungerade Primzahl p ist Teiler einer Zahl [mm] n^{2} +1 [/mm] mit [mm] n \in \IN [/mm] genau dann, wenn p [mm] \equiv [/mm] 1 (mod 4)gilt. |
Hallo,
hab schon ewig rumprobiert und kriegs net hin. Ein kleiner Tipp wäre toll!
Vielen Dank
teo
|
|
|
|
Falls [mm] $p\in\mathbb{P}$ [/mm] ungerade ist gibt es nur zwei Möglichkeiten:
Fall 1: [mm] $p\equiv 1\mod [/mm] 4$ (<- wir wären fertig)
Fall 2: [mm] $p\equiv 3\mod [/mm] 4$
Annahme: [mm] $p\equiv 3\mod [/mm] 4$
Aus [mm] $n^2\equiv [/mm] -1 [mm] \mod [/mm] p$ folgt [mm] $n^4\equiv [/mm] 1 [mm] \mod [/mm] p$
Laut Annahme ist $p=4k+3$ für ein k
Konstruiere nun ein Widerspruch zum kleinen Satz von Fermat [mm] $n^{p-1}\equiv [/mm] 1 [mm] \mod [/mm] p$.
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 10:26 Di 08.05.2012 | Autor: | felixf |
Moin!
> Es ist ja zu zeigen [mm]n^2\equiv -1 \mod p\gdw p\equiv 1\mod 4[/mm].
Die Aussage ist so falsch: es gibt unendlich viele Primzahlen $p$ mit $p [mm] \equiv [/mm] 1 [mm] \pmod{4}$, [/mm] jedoch nur endlich viele Primteiler von [mm] $n^2 [/mm] + 1$.
Ich glaube, hier soll nur [mm] "$\Rightarrow$" [/mm] gezeigt werden, also: jeder ungerade Primteiler von [mm] $n^2 [/mm] + 1$ ist kongruent zu 1 modulo 4.
LG Felix
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 16:38 Di 08.05.2012 | Autor: | wieschoo |
Da habe ich mich böse vertan. Ich hatte die ganze Zeit die Aussage
"Eine Primzahl [mm]p[/mm] kann genau dann als Summe 2er Quadrate geschrieben
werden, falls [mm]p=2[/mm] oder [mm]p \equiv 1 \pmod 4[/mm] gilt. "
Sorry. Habs korrigiert.
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 22:14 Di 08.05.2012 | Autor: | teo |
ah! entschuldigung hab die antwort von felix nicht richtig gelesen bzw. nicht sofort kapiert... alles klar! vielen dank!
grüße
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 18:01 Di 08.05.2012 | Autor: | teo |
Hallo,
danke für die Antwort!
> Falls [mm]p\in\mathbb{P}[/mm] ungerade ist gibt es nur zwei
> Möglichkeiten:
>
> Fall 1: [mm]p\equiv 1\mod 4[/mm] (<- wir wären fertig)
> Fall 2: [mm]p\equiv 3\mod 4[/mm]
>
> Annahme: [mm]p\equiv 3\mod 4[/mm]
> Aus [mm]n^2\equiv -1 \mod p[/mm] folgt
> [mm]n^4\equiv 1 \mod p[/mm]
> Laut Annahme ist [mm]p=4k+3[/mm] für ein k
>
> Konstruiere nun ein Widerspruch zum kleinen Satz von Fermat
> [mm]n^{p-1}\equiv 1 \mod p[/mm].
Also wenn [mm]n^{4} \equiv 1 \mod p[/mm] ist, dann folgt aus dem Satz von Fermat, das p = 5 ist. Dies ist aber ein Widerspruch zu [mm]p = 4k + 3[/mm] für ein [mm]k \in \IZ[/mm]. Da kein solches k existiert, sodass [mm]5 = 4k + 3[/mm] gilt.
Reicht das schon als Beweis aus? Was ist mit der Gegenrichtung, die müsste man bei der Aufgabenstellung doch eigentlich schon auch machen.
Vielen Dank!
Grüße
|
|
|
|
|
> Hallo,
> danke für die Antwort!
>
> > Falls [mm]p\in\mathbb{P}[/mm] ungerade ist gibt es nur zwei
> > Möglichkeiten:
> >
> > Fall 1: [mm]p\equiv 1\mod 4[/mm] (<- wir wären fertig)
> > Fall 2: [mm]p\equiv 3\mod 4[/mm]
> >
> > Annahme: [mm]p\equiv 3\mod 4[/mm]
> > Aus [mm]n^2\equiv -1 \mod p[/mm]
> folgt
> > [mm]n^4\equiv 1 \mod p[/mm]
> > Laut Annahme ist [mm]p=4k+3[/mm] für ein
> k
> >
> > Konstruiere nun ein Widerspruch zum kleinen Satz von Fermat
> > [mm]n^{p-1}\equiv 1 \mod p[/mm].
>
> Also wenn [mm]n^{4} \equiv 1 \mod p[/mm] ist, dann folgt aus dem
> Satz von Fermat, das p = 5 ist. Dies ist aber ein
Dann solltest du noch einmal nachschauen, was der Satz von Fermat wirklich sagt.
Zum Beispiel ist [mm]1^4\equiv 1 \mod r[/mm] für alle r!
> Widerspruch zu [mm]p = 4k + 3[/mm] für ein [mm]k \in \IZ[/mm]. Da kein
> solches k existiert, sodass [mm]5 = 4k + 3[/mm] gilt.
Du weißt doch [mm]n^4\equiv 1\mod p[/mm]. Laut Annahme [mm] ($p\equiv 3\mod [/mm] 4$) ist [mm]p=4k+3\;[/mm]
[mm]n^{p-1}=n^{4k+3-1}=n^{4k+2}=\ldots=-1[/mm]
Aber nach Fermat muss [mm]n^{p-1}\equiv 1\mod p[/mm] sein.
>
> Reicht das schon als Beweis aus? Was ist mit der
> Gegenrichtung, die müsste man bei der Aufgabenstellung
> doch eigentlich schon auch machen.
Da hat mich Felix überzeugt:
https://matheraum.de/read?i=886855
>
> Vielen Dank!
>
> Grüße
>
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 14:14 Mi 09.05.2012 | Autor: | teo |
Hallo,
habe zu [mm] "\Leftarrow" [/mm] trotzdem noch eine Frage. Das ist doch trotzdem möglich. Diese Richtung ist doch nur ein Existenzbeweis für n. Also für alle ungeraden Primzahlen mit [mm]p \equiv 1\mod p [/mm] existiert ein n [mm] \in \IN, [/mm] sodass [mm] n^{2} \equiv -1 \mod p[/mm].
Die Aussage stimmt doch so, also müsste die doch auch zu beweisen sein.
Vielen Dank!
Grüße
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 16:23 Mi 09.05.2012 | Autor: | felixf |
Moin,
> habe zu [mm]"\Leftarrow"[/mm] trotzdem noch eine Frage. Das ist doch
> trotzdem möglich. Diese Richtung ist doch nur ein
> Existenzbeweis für n. Also für alle ungeraden Primzahlen
> mit [mm]p \equiv 1\mod p[/mm] existiert ein n [mm]\in \IN,[/mm] sodass [mm]n^{2} \equiv -1 \mod p[/mm].
> Die Aussage stimmt doch so, also müsste die doch auch zu
> beweisen sein.
stimmt, da hast du Recht. Diese Richtung kann man auch beweisen. Das Problem ist halt die Klammerung Also wo man das $n$ hinpackt und wo nicht bei der Aussage.
LG Felix
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 16:57 Mi 09.05.2012 | Autor: | teo |
Hallo
> Moin,
>
> > habe zu [mm]"\Leftarrow"[/mm] trotzdem noch eine Frage. Das ist doch
> > trotzdem möglich. Diese Richtung ist doch nur ein
> > Existenzbeweis für n. Also für alle ungeraden Primzahlen
> > mit [mm]p \equiv 1\mod p[/mm] existiert ein n [mm]\in \IN,[/mm] sodass [mm]n^{2} \equiv -1 \mod p[/mm].
> > Die Aussage stimmt doch so, also müsste die doch auch zu
> > beweisen sein.
>
> stimmt, da hast du Recht. Diese Richtung kann man auch
> beweisen. Das Problem ist halt die Klammerung Also wo
> man das [mm]n[/mm] hinpackt und wo nicht bei der Aussage.
>
> LG Felix
>
Und wie könnts gehen?
Danke
|
|
|
|
|
Status: |
(Antwort) fertig | Datum: | 21:15 Mi 09.05.2012 | Autor: | felixf |
Moin!
> > > habe zu [mm]"\Leftarrow"[/mm] trotzdem noch eine Frage. Das ist doch
> > > trotzdem möglich. Diese Richtung ist doch nur ein
> > > Existenzbeweis für n. Also für alle ungeraden Primzahlen
> > > mit [mm]p \equiv 1\mod p[/mm] existiert ein n [mm]\in \IN,[/mm] sodass [mm]n^{2} \equiv -1 \mod p[/mm].
> > > Die Aussage stimmt doch so, also müsste die doch auch zu
> > > beweisen sein.
> >
> > stimmt, da hast du Recht. Diese Richtung kann man auch
> > beweisen. Das Problem ist halt die Klammerung Also wo
> > man das [mm]n[/mm] hinpackt und wo nicht bei der Aussage.
> >
> > LG Felix
> >
> Und wie könnts gehen?
Die Einheitengruppe [mm] $(\IZ/p\IZ)^\ast$ [/mm] ist zyklisch. Welche Ordnung hat sie? Gibt es ein Element der Ordnung 4?
LG Felix
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 08:24 Do 10.05.2012 | Autor: | teo |
> Moin!
>
> > > > habe zu [mm]"\Leftarrow"[/mm] trotzdem noch eine Frage. Das ist doch
> > > > trotzdem möglich. Diese Richtung ist doch nur ein
> > > > Existenzbeweis für n. Also für alle ungeraden Primzahlen
> > > > mit [mm]p \equiv 1\mod 4[/mm] existiert ein n [mm]\in \IN,[/mm] sodass [mm]n^{2} \equiv -1 \mod p[/mm].
> > > > Die Aussage stimmt doch so, also müsste die doch auch zu
> > > > beweisen sein.
> > >
> > > stimmt, da hast du Recht. Diese Richtung kann man auch
> > > beweisen. Das Problem ist halt die Klammerung Also wo
> > > man das [mm]n[/mm] hinpackt und wo nicht bei der Aussage.
> > >
> > > LG Felix
> > >
> > Und wie könnts gehen?
>
> Die Einheitengruppe [mm](\IZ/p\IZ)^\ast[/mm] ist zyklisch. Welche
> Ordnung hat sie? Gibt es ein Element der Ordnung 4?
>
> LG Felix
>
Hallo,
für die Einheitengruppe gilt #[mm](\IZ/p\IZ)^\ast[/mm] = p-1. Da nach Voraussetzung [mm]p\equiv 1 \mod 4 \gdw p-1 \equiv 0\mod 4[/mm] ist p-1 durch 4 teilbar. Also ex., da [mm](\IZ/p\IZ)^\ast[/mm] zyklisch ist für jeden Teiler der Gruppenordnung ein Element dieser Ordnung. Also gibt es ein Element der Ordnung 4 in [mm](\IZ/p\IZ)^\ast[/mm].
Ok aber wie komm ich jetzt dahin, dass ein [mm]n \in \IN[/mm] existiert mit [mm] n^{2}\equiv -1 \mod p[/mm]? Ich sehs leider nicht.
Vielen Dank!
Grüße
|
|
|
|
|
Und ein Element der Ordnung 4 erfüllt [mm] $x^2+1=0$ [/mm] in [mm] $\IF_p$.[/mm]
|
|
|
|
|
Status: |
(Frage) beantwortet | Datum: | 16:39 Do 10.05.2012 | Autor: | teo |
> in [mm]\IF_p[/mm] gilt
>
> [mm]x^4-1=(x^2+1)(x^2-1)[/mm]
>
>
Für ein Element a mit Ordnung vier gilt [mm] a^{4}=1, [/mm] also gilt [mm]a^{4}-1=(a^{2}-1)(a^{2}+1)=0 \Rightarrow (a^{2}-1)(a^{2}+1) = 1.[/mm]
Hm.. das bringt mich jetzt aber auch net weiter.. Ich brauch doch [mm]n^{2} \equiv -1 \mod p[/mm]
Seht ihr die Lösung schon? Ich würds wirklich auch gern kapieren!
Vielen Dank!
|
|
|
|
|
Letzlich musst du nur zeigen, dass die Quadradtwurzel von [mm]-1[/mm] in [mm] $\IZ/p\IZ$ [/mm] vorhanden ist.
Es ist doch
[mm]n^4-1=(n^2-1)(n^2+1)[/mm]
Die Lösungen von [mm]n^2-1[/mm] sind [mm]\pm 1[/mm]. Eine Lösung von [mm]n^2+1[/mm] ist [mm]k[/mm] mit [mm]k^2=-1[/mm]. Und dieses k hat nun dann die Ordnung vier.
Allgemeiner gilt:
Es gibt ein Element [mm] $a\in\IF_{p^r}$ [/mm] mit ord(a)=k <=> [mm] $k\mid p^{r}-1$
[/mm]
|
|
|
|
|
Status: |
(Mitteilung) Reaktion unnötig | Datum: | 17:13 Do 10.05.2012 | Autor: | teo |
Danke! Jetzt hab ichs kapiert!
|
|
|
|