Verschiedene Fragen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:38 Di 13.10.2009 | | Autor: | Leni-H |
Hallo!
Ich bin gerade dabei, einen Beweis zu verstehen und habe einige einzelne Fragen, von denen ich hoffe, dass ihr sie beantworten könnt:
1) Wenn ich weiß, dass [mm] c^{\bruch{p-1}{2}} \equiv [/mm] 1 (mod p), wie folgt dann induktiv, dass [mm] c^{\bruch{(p-1)p^{a-1}}{2}} \equiv [/mm] 1 (mod [mm] p^{a})?
[/mm]
In dem Beweis steht nur, dass das induktiv leicht folgt, aber ich komm nicht drauf wie und warum!?
2) Wenn ich weiß, dass c quadratischer Rest modulo [mm] 2^{a_{0}} [/mm] und c auch quadratischer Rest modulo [mm] p_{j}^{a_{j}} [/mm] für alle j, wieso gilt dann auch, dass c quadratischer Rest modulo [mm] m=2^{a_{0}} \produkt_{p_{j}}^{}p_{j}^{a_{j}}
[/mm]
Wie kann man das folgern???
Vielen Dank für eure Bemühungen!
LG Leni
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 16:33 Di 13.10.2009 | | Autor: | felixf |
Hallo!
> 1) Wenn ich weiß, dass [mm]c^{\bruch{p-1}{2}} \equiv[/mm] 1 (mod
> p), wie folgt dann induktiv, dass
> [mm]c^{\bruch{(p-1)p^{a-1}}{2}} \equiv[/mm] 1 (mod [mm]p^{a})?[/mm]
> In dem Beweis steht nur, dass das induktiv leicht folgt,
> aber ich komm nicht drauf wie und warum!?
Du machst Induktion nach $a$. Der Anfang mit $a = 1$ ist die Voraussetzung, dir fehlt also der Induktionsschritt.
Du weisst, dass [mm] $c^{(p - 1) p^{a-1}/2} \equiv [/mm] 1 [mm] \pmod{p^a}$ [/mm] ist, also ist [mm] $c^{(p - 1) p^{a-1}/2} [/mm] = 1 + k [mm] p^a \pmod{p^{a+1}}$ [/mm] mit $k [mm] \in \{ 0, \dots, p-1 \}$. [/mm] Jetzt willst du das ganze hoch $p$ nehmen, um zu zeigen, dass [mm] $c^{(p - 1) p^a/2} [/mm] = [mm] (c^{(p - 1) p^{a-1}/2})^p \equiv [/mm] 1 [mm] \pmod{p^{a+1}}$ [/mm] ist.
> 2) Wenn ich weiß, dass c quadratischer Rest modulo
> [mm]2^{a_{0}}[/mm] und c auch quadratischer Rest modulo
> [mm]p_{j}^{a_{j}}[/mm] für alle j, wieso gilt dann auch, dass c
> quadratischer Rest modulo [mm]m=2^{a_{0}} \produkt_{p_{j}}^{}p_{j}^{a_{j}}[/mm]
Chinesischer Restsatz.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 19:39 Di 13.10.2009 | | Autor: | Leni-H |
Vielen Dank erstmal!
>
> > 1) Wenn ich weiß, dass [mm]c^{\bruch{p-1}{2}} \equiv[/mm] 1 (mod
> > p), wie folgt dann induktiv, dass
> > [mm]c^{\bruch{(p-1)p^{a-1}}{2}} \equiv[/mm] 1 (mod [mm]p^{a})?[/mm]
> > In dem Beweis steht nur, dass das induktiv leicht
> folgt,
> > aber ich komm nicht drauf wie und warum!?
>
> Du machst Induktion nach [mm]a[/mm]. Der Anfang mit [mm]a = 1[/mm] ist die
> Voraussetzung, dir fehlt also der Induktionsschritt.
>
> Du weisst, dass [mm]c^{(p - 1) p^{a-1}/2} \equiv 1 \pmod{p^a}[/mm]
> ist, also ist [mm]c^{(p - 1) p^{a-1}/2} = 1 + k p^a \pmod{p^{a+1}}[/mm]
> mit [mm]k \in \{ 0, \dots, p-1 \}[/mm]. Jetzt willst du das ganze
> hoch [mm]p[/mm] nehmen, um zu zeigen, dass [mm]c^{(p - 1) p^a/2} = (c^{(p - 1) p^{a-1}/2})^p \equiv 1 \pmod{p^{a+1}}[/mm]
> ist.
Aber wenn ich dann das Ganze hoch p nehme, hab ich ja [mm] (1+kp^{a})^{p}. [/mm] Und wieso ergibt das dann 1?
>
> > 2) Wenn ich weiß, dass c quadratischer Rest modulo
> > [mm]2^{a_{0}}[/mm] und c auch quadratischer Rest modulo
> > [mm]p_{j}^{a_{j}}[/mm] für alle j, wieso gilt dann auch, dass c
> > quadratischer Rest modulo [mm]m=2^{a_{0}} \produkt_{p_{j}}^{}p_{j}^{a_{j}}[/mm]
>
> Chinesischer Restsatz.
>
> LG Felix
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:55 Di 13.10.2009 | | Autor: | felixf |
Hallo!
> > > 1) Wenn ich weiß, dass [mm]c^{\bruch{p-1}{2}} \equiv[/mm] 1 (mod
> > > p), wie folgt dann induktiv, dass
> > > [mm]c^{\bruch{(p-1)p^{a-1}}{2}} \equiv[/mm] 1 (mod [mm]p^{a})?[/mm]
> > > In dem Beweis steht nur, dass das induktiv leicht
> > folgt,
> > > aber ich komm nicht drauf wie und warum!?
> >
> > Du machst Induktion nach [mm]a[/mm]. Der Anfang mit [mm]a = 1[/mm] ist die
> > Voraussetzung, dir fehlt also der Induktionsschritt.
> >
> > Du weisst, dass [mm]c^{(p - 1) p^{a-1}/2} \equiv 1 \pmod{p^a}[/mm]
> > ist, also ist [mm]c^{(p - 1) p^{a-1}/2} = 1 + k p^a \pmod{p^{a+1}}[/mm]
> > mit [mm]k \in \{ 0, \dots, p-1 \}[/mm]. Jetzt willst du das ganze
> > hoch [mm]p[/mm] nehmen, um zu zeigen, dass [mm]c^{(p - 1) p^a/2} = (c^{(p - 1) p^{a-1}/2})^p \equiv 1 \pmod{p^{a+1}}[/mm]
> > ist.
>
> Aber wenn ich dann das Ganze hoch p nehme, hab ich ja
> [mm](1+kp^{a})^{p}.[/mm] Und wieso ergibt das dann 1?
Na, es ist doch $(1 + k [mm] p^a)^p [/mm] = [mm] \sum_{i=0}^p \binom{p}{i} k^i p^{i a}$. [/mm] Jetzt schau dir alle Summanden getrennt an. Der erste ist offensichtlich 1. Jetzt ueberleg dir, warum alle anderen durch [mm] $p^{a + 1}$ [/mm] teilbar sind und somit 0 modulo [mm] $p^{a + 1}$ [/mm] sind.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:48 Mi 14.10.2009 | | Autor: | Leni-H |
Hi!
Ich habe nochmal eine kleine Frage zu 2):
>
> > 1) Wenn ich weiß, dass [mm]c^{\bruch{p-1}{2}} \equiv[/mm] 1 (mod
> > p), wie folgt dann induktiv, dass
> > [mm]c^{\bruch{(p-1)p^{a-1}}{2}} \equiv[/mm] 1 (mod [mm]p^{a})?[/mm]
> > In dem Beweis steht nur, dass das induktiv leicht
> folgt,
> > aber ich komm nicht drauf wie und warum!?
>
> Du machst Induktion nach [mm]a[/mm]. Der Anfang mit [mm]a = 1[/mm] ist die
> Voraussetzung, dir fehlt also der Induktionsschritt.
>
> Du weisst, dass [mm]c^{(p - 1) p^{a-1}/2} \equiv 1 \pmod{p^a}[/mm]
> ist, also ist [mm]c^{(p - 1) p^{a-1}/2} = 1 + k p^a \pmod{p^{a+1}}[/mm]
> mit [mm]k \in \{ 0, \dots, p-1 \}[/mm]. Jetzt willst du das ganze
> hoch [mm]p[/mm] nehmen, um zu zeigen, dass [mm]c^{(p - 1) p^a/2} = (c^{(p - 1) p^{a-1}/2})^p \equiv 1 \pmod{p^{a+1}}[/mm]
> ist.
>
> > 2) Wenn ich weiß, dass c quadratischer Rest modulo
> > [mm]2^{a_{0}}[/mm] und c auch quadratischer Rest modulo
> > [mm]p_{j}^{a_{j}}[/mm] für alle j, wieso gilt dann auch, dass c
> > quadratischer Rest modulo [mm]m=2^{a_{0}} \produkt_{p_{j}}^{}p_{j}^{a_{j}}[/mm]
>
> Chinesischer Restsatz.
Wie folgt das genau mit dem Chinesischen Restsatz?? Kann ich das folgendermaßen begründen: c ist ein Quadrat im Ring [mm] \IZ|m\IZ, [/mm] weil c ein Quadrat in den Ringen [mm] \IZ|2^{a_{0}}\IZ, \IZ|p_{j}\IZ [/mm] für alle j ist und es einen Isomorphismus von [mm] \IZ|2^{a_{0}}\IZ [/mm] x [mm] \IZ|p_{1}\IZ [/mm] x [mm] \IZ|p_{2}\IZ [/mm] x .... nach [mm] \IZ|m\IZ [/mm] gibt?
Oder wie genau kann man das mit dem Chinesischen Restsatz begründen?
Danke!
LG Leni
>
> LG Felix
>
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:05 Do 15.10.2009 | | Autor: | felixf |
Hallo!
> > > 2) Wenn ich weiß, dass c quadratischer Rest modulo
> > > [mm]2^{a_{0}}[/mm] und c auch quadratischer Rest modulo
> > > [mm]p_{j}^{a_{j}}[/mm] für alle j, wieso gilt dann auch, dass c
> > > quadratischer Rest modulo [mm]m=2^{a_{0}} \produkt_{p_{j}}^{}p_{j}^{a_{j}}[/mm]
> >
> > Chinesischer Restsatz.
>
> Wie folgt das genau mit dem Chinesischen Restsatz?? Kann
> ich das folgendermaßen begründen: c ist ein Quadrat im
> Ring [mm]\IZ|m\IZ,[/mm] weil c ein Quadrat in den Ringen
> [mm]\IZ|2^{a_{0}}\IZ, \IZ|p_{j}\IZ[/mm] für alle j ist und es einen
> Isomorphismus von [mm]\IZ|2^{a_{0}}\IZ[/mm] x [mm]\IZ|p_{1}\IZ[/mm] x
> [mm]\IZ|p_{2}\IZ[/mm] x .... nach [mm]\IZ|m\IZ[/mm] gibt?
> Oder wie genau kann man das mit dem Chinesischen Restsatz
> begründen?
Fast. Wenn du [mm] $p_1, p_2, \dots$ [/mm] jetzt noch durch [mm] $p_1^{a_1}, p_2^{a_2}, \dots$ [/mm] ersetzt, dann stimmt es.
(Modulo wird uebrigens als / und nicht | geschrieben.)
LG Felix
|
|
|
|
