Quadratischer Rest < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 09:32 Di 28.06.2011 | | Autor: | Loriot95 |
| Aufgabe | Es sei p [mm] \in \IP [/mm] eine Primzahl, k [mm] \in \IZ_{>0} [/mm] und a = [mm] p^{m}*b \in \IZ [/mm] mit ggt(b,p) = 1.
Ist [mm] 0\le [/mm] m < k, so sind die folgenden Aussagen Äquivalent:
(a) [mm] x^{2} \equiv [/mm] a (mod [mm] p^{k}) [/mm] hat eine Lösung in [mm] \IZ
[/mm]
(b) m ist gerade und die Gleichung [mm] y^{2} \equiv [/mm] b (mod [mm] p^{k-m}) [/mm] ist in [mm] \IZ [/mm] lösbar. |
Guten Morgen,
habe der obigen Aufgabe Schwierigkeiten. Hab folgendes versucht:
(a) [mm] \Rightarrow [/mm] (b): [mm] \exists [/mm] x [mm] \in \IZ: x^{2} \equiv [/mm] a (mod [mm] p^{k}) \Rightarrow [/mm] a = [mm] x^{2}+c*p^{k} [/mm] für ein c [mm] \in \IZ. [/mm] d.h [mm] x^{2} [/mm] = [mm] p^{m}(b-c*p^{k-m}). [/mm] Nun müsste ich irgendwie zeigen, dass [mm] b-c*p^{k-m} [/mm] = [mm] y^{2} [/mm] ist und das m = 2n für ein n [mm] \in \IZ [/mm] ist. Leider komme ich hier nicht weiter. Würde mich über einen Tipp freuen.
LG Loriot95
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 11:28 Di 28.06.2011 | | Autor: | felixf |
Moin!
> Es sei p [mm]\in \IP[/mm] eine Primzahl, k [mm]\in \IZ_{>0}[/mm] und a =
> [mm]p^{m}*b \in \IZ[/mm] mit ggt(b,p) = 1.
>
> Ist [mm]0\le[/mm] m < k, so sind die folgenden Aussagen
> Äquivalent:
> (a) [mm]x^{2} \equiv[/mm] a (mod [mm]p^{k})[/mm] hat eine Lösung in [mm]\IZ[/mm]
> (b) m ist gerade und die Gleichung [mm]y^{2} \equiv[/mm] b (mod
> [mm]p^{k-m})[/mm] ist in [mm]\IZ[/mm] lösbar.
> Guten Morgen,
>
> habe der obigen Aufgabe Schwierigkeiten. Hab folgendes
> versucht:
> (a) [mm]\Rightarrow[/mm] (b): [mm]\exists[/mm] x [mm]\in \IZ: x^{2} \equiv[/mm] a
> (mod [mm]p^{k}) \Rightarrow[/mm] a = [mm]x^{2}+c*p^{k}[/mm] für ein c [mm]\in \IZ.[/mm]
> d.h [mm]x^{2}[/mm] = [mm]p^{m}(b-c*p^{k-m}).[/mm] Nun müsste ich irgendwie
> zeigen, dass [mm]b-c*p^{k-m}[/mm] = [mm]y^{2}[/mm] ist und das m = 2n für
> ein n [mm]\in \IZ[/mm] ist. Leider komme ich hier nicht weiter.
$b - c [mm] p^{k - m}$ [/mm] ist eine ganze Zahl, die nicht durch $p$ teilbar ist (warum?). Mit der Eindeutigkeit der Primfaktorzerlegung folgt also aus [mm] $x^2 [/mm] = [mm] p^m [/mm] (b - c [mm] p^{k - m})$, [/mm] dass $m$ gerade sein muss und dass [mm] $(x/p^{m/2})^2 [/mm] = b - c [mm] p^{k - m}$ [/mm] ist.
LG Felix
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:37 Di 28.06.2011 | | Autor: | Loriot95 |
> [mm]b - c p^{k - m}[/mm] ist eine ganze Zahl, die nicht durch [mm]p[/mm]
> teilbar ist (warum?).
Weil ggt(b,p) = 1.
Mit der Eindeutigkeit der
> Primfaktorzerlegung folgt also aus [mm]x^2 = p^m (b - c p^{k - m})[/mm],
> dass [mm]m[/mm] gerade sein muss und dass [mm](x/p^{m/2})^2 = b - c p^{k - m}[/mm]
> ist.
>
> LG Felix
>
Ich sehe noch nicht wirklich weshalb daraus folgt das m gerade sein muss. Also es ist
b - c [mm] p^{k - m} [/mm] = [mm] p_{1}^{n1}*...*p_{k}^{n_{k}} [/mm] wobei [mm] p_{i} \not= [/mm] p für alle i = 1,..,k und [mm] n_{i} \in \IN, p_{i} \in \IP. [/mm] Somit ist [mm] x^{2} [/mm] = [mm] p^{m}*(p_{1}^{n1}*...*p_{k}^{n_{k}}). [/mm] Mal angenommen m wäre gerade d.h m = 2n für ein n [mm] \in \IN. [/mm] Dann muss auch müssen auch alle [mm] n_{i} [/mm] gerade Zahlen sein. Oder sehe ich das völlig falsch? Und wie zeigt man das?
LG Loriot95
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 16:52 Di 28.06.2011 | | Autor: | felixf |
Moin!
> > [mm]b - c p^{k - m}[/mm] ist eine ganze Zahl, die nicht durch [mm]p[/mm]
> > teilbar ist (warum?).
> Weil ggt(b,p) = 1.
Und da $c [mm] p^{k - m}$ [/mm] durch $p$ teilbar ist, weil $k > m$ ist.
> > Mit der Eindeutigkeit der
> > Primfaktorzerlegung folgt also aus [mm]x^2 = p^m (b - c p^{k - m})[/mm],
> > dass [mm]m[/mm] gerade sein muss und dass [mm](x/p^{m/2})^2 = b - c p^{k - m}[/mm]
> > ist.
>
> Ich sehe noch nicht wirklich weshalb daraus folgt das m
> gerade sein muss. Also es ist
> b - c [mm]p^{k - m}[/mm] = [mm]p_{1}^{n1}*...*p_{k}^{n_{k}}[/mm] wobei [mm]p_{i} \not=[/mm]
> p für alle i = 1,..,k und [mm]n_{i} \in \IN, p_{i} \in \IP.[/mm]
![[ok]](/images/smileys/ok.gif "[ok]")
> Somit ist [mm]x^{2}[/mm] = [mm]p^{m}*(p_{1}^{n1}*...*p_{k}^{n_{k}}).[/mm]
> Mal angenommen m wäre gerade d.h m = 2n für ein n [mm]\in \IN.[/mm]
> Dann muss auch müssen auch alle [mm]n_{i}[/mm] gerade Zahlen sein.
> Oder sehe ich das völlig falsch? Und wie zeigt man das?
Ja, alle Exponenten muessen gerade sein.
Es ist ja so, dass $x$ keine anderen Primfaktoren als $p, [mm] p_1, \dots, p_k$ [/mm] enthalten kann. Also gilt $x = [mm] p^e \cdot p^{e_1} \cdots p_k^{e_k}$, [/mm] und somit [mm] $p^{2 e} \cdot p^{2 e_1} \cdots p_k^{2 e_k} [/mm] = [mm] \left( p^e \cdot p^{e_1} \cdots p_k^{e_k} \right)^2 [/mm] = [mm] p^m \cdot p_1^{n_1} \cdots p_k^{n_k}$. [/mm] Jetzt folgt aus der Eindeutigkeit der Primfaktorzerlegung, dass $2 e = m$ und $2 [mm] e_i [/mm] = [mm] n_i$ [/mm] fuer alle $i$ ist.
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:57 Di 28.06.2011 | | Autor: | Loriot95 |
Dann bedanke ich mich. Die Richtung (b) [mm] \Rightarrow [/mm] (a) habe ich selbst hinbekommen. Danke schön :).
LG Loriot95
|
|
|
|
