Quadratische Reste < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:13 Sa 03.12.2011 | | Autor: | swetti |
| Aufgabe | für ungerade v und [mm] r\ge3 [/mm] zeige:
[mm] x^{2} \equiv [/mm] v mod [mm] 2^{r} [/mm] lösbar [mm] \gdw [/mm] v [mm] \equiv [/mm] 1 mod 8 |
Diese Ausage haben wir in der vorlesung behandelt und dazu folgendes aufgeschrieben:
[mm] \Rightarrow [/mm] : Es gibt ein x [mm] \in \IZ, [/mm] welches die Gleichung [mm] x^{2} \equiv [/mm] v mod [mm] 2^{r} [/mm] löst. Da v ungerade nach Voraussetzung, muss auch x ungerade sein. Also ist [mm] x^{2} \equiv [/mm] 1 mod 8 und damit r [mm] \equiv [/mm] 1 mod 8.
...das ist mir auch klar...
[mm] \Leftarrow [/mm] :
(1) Ist r [mm] \equiv [/mm] 1 mod 8, dann ist [mm] x^{2} \equiv [/mm] v mod [mm] 2^{r} [/mm] für r=3 lösbar.
...auch klar....
(2) Sei [mm] x_{0} [/mm] eine Lösung dieser Kongruenz für ein r [mm] \ge [/mm] 3.
...darf man das einfach so festlegen bzw. voraussetzen?...
(3) Nun bestimme ein t so, dass [mm] x_{0} [/mm] + [mm] 2^{r-1}*t [/mm] eine Lösung von [mm] x^{2} \equiv [/mm] v mod [mm] 2^{r+1}.
[/mm]
Dann: [mm] (x_{0} [/mm] + [mm] 2^{r-1} *t)^{2} \equiv x_{0}^{2} [/mm] + [mm] 2^{r}x_{0}t [/mm] + [mm] 2^{2r-2}t^{2} \equiv x_{0}^{2} [/mm] + [mm] 2^{r}x_{0}t [/mm] mod [mm] 2^{r+1}, [/mm] da für [mm] r\ge [/mm] 3 gilt, dass 2r-2 [mm] \ge [/mm] r+1 und damit [mm] 2^{r+1} [/mm] ein echter Teiler von [mm] 2^{2r-2} [/mm] ist.
Mit [mm] x_{0}t \equiv \bruch{v-x_{0}^{2}}{2^{r}} [/mm] mod 2 (also t = 0 oder t = 1) gilt dann [mm] x_{0}^{2} [/mm] + [mm] 2^{r}x_{0}t \equiv [/mm] v mod [mm] 2^{r+1}.
[/mm]
...Ich verstehe nicht, woher man hier auf die Lösung [mm] x_{0} [/mm] + [mm] 2^{r-1}*t [/mm] kommt? Wurde sie geschickt gewählt oder ausgerechnet? Das erinnert mich so n bißchen an homogene+spezielle Lösung, wüsste aber nicht wie man das auf die Modulrechnung anwenden sollte......
....Und auch den Zusatz mit t = 0 oder t = 1 kann ich nicht wirklich einordnen. Habe versucht, dies in [mm] x_{0}^{2} [/mm] + [mm] 2^{r}x_{0}t [/mm] oder in [mm] x_{0}^{2} [/mm] + [mm] 2^{r}x_{0}t [/mm] + [mm] 2^{2r-2}t^{2} [/mm] einzusetzen und mir die Aussage dann anzugucken, aber das hat mit irgendwie nicht geholfen. Oder ich seh oder versteh das nicht......
Es wäre wirklich sehr hilfreich für mich, wenn man mir hier ein paar Tipps oder Hinweise zu (2) und (3) geben könnte. Ich würde sehr gerne diesen Schritt verstehen.
Ich bedanke mich herzlich im Vorraus für eure Mühe.
Vlg swetti
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 10:18 Mo 05.12.2011 | | Autor: | felixf |
Moin swetti!
> für ungerade v und [mm]r\ge3[/mm] zeige:
> [mm]x^{2} \equiv[/mm] v mod [mm]2^{r}[/mm] lösbar [mm]\gdw[/mm] v [mm]\equiv[/mm] 1 mod 8
> Diese Ausage haben wir in der vorlesung behandelt und dazu
> folgendes aufgeschrieben:
>
> [mm]\Rightarrow[/mm] : Es gibt ein x [mm]\in \IZ,[/mm] welches die Gleichung
> [mm]x^{2} \equiv[/mm] v mod [mm]2^{r}[/mm] löst. Da v ungerade nach
> Voraussetzung, muss auch x ungerade sein. Also ist [mm]x^{2} \equiv[/mm]
> 1 mod 8 und damit r [mm]\equiv[/mm] 1 mod 8.
> ...das ist mir auch klar...
![[ok]](/images/smileys/ok.gif "[ok]")
> [mm]\Leftarrow[/mm] :
> (1) Ist r [mm]\equiv[/mm] 1 mod 8, dann ist [mm]x^{2} \equiv[/mm] v mod [mm]2^{r}[/mm]
> für r=3 lösbar.
> ...auch klar....
>
> (2) Sei [mm]x_{0}[/mm] eine Lösung dieser Kongruenz für ein r [mm]\ge[/mm]
> 3.
> ...darf man das einfach so festlegen bzw. voraussetzen?...
Das ist eine Induktionsvoraussetzung. Insofern: ja.
Hier wird per Induktion gezeigt, dass aus $v [mm] \equiv [/mm] 1 [mm] \pmod{8}$ [/mm] folgt, dass [mm] $x^2 \equiv [/mm] v [mm] \pmod{2^r}$ [/mm] fuer alle $r [mm] \ge [/mm] 3$ loesbar ist.
> (3) Nun bestimme ein t so, dass [mm]x_{0}[/mm] + [mm]2^{r-1}*t[/mm] eine
> Lösung von [mm]x^{2} \equiv[/mm] v mod [mm]2^{r+1}.[/mm]
> Dann: [mm](x_{0}[/mm] + [mm]2^{r-1} *t)^{2} \equiv x_{0}^{2}[/mm] +
> [mm]2^{r}x_{0}t[/mm] + [mm]2^{2r-2}t^{2} \equiv x_{0}^{2}[/mm] + [mm]2^{r}x_{0}t[/mm]
> mod [mm]2^{r+1},[/mm] da für [mm]r\ge[/mm] 3 gilt, dass 2r-2 [mm]\ge[/mm] r+1 und
> damit [mm]2^{r+1}[/mm] ein echter Teiler von [mm]2^{2r-2}[/mm] ist.
> Mit [mm]x_{0}t \equiv \bruch{v-x_{0}^{2}}{2^{r}}[/mm] mod 2 (also t
> = 0 oder t = 1) gilt dann [mm]x_{0}^{2}[/mm] + [mm]2^{r}x_{0}t \equiv[/mm]
> v mod [mm]2^{r+1}.[/mm]
> ...Ich verstehe nicht, woher man hier auf die Lösung
> [mm]x_{0}[/mm] + [mm]2^{r-1}*t[/mm] kommt? Wurde sie geschickt gewählt oder
> ausgerechnet?
Nun, du hast schon eine Loesung modulo [mm] $2^r$ [/mm] (und zwar [mm] $x_0$). [/mm] Dies ist aber im Allgemeinen keine Loesung modulo [mm] $2^{r+1}$. [/mm] Die Frage ist nun, wie du [mm] $x_0$ [/mm] "minimal" abaendern kannst, um eine Loesung modulo [mm] $2^{r+1}$ [/mm] zu erhalten.
Der Trick ist nun, etwas so kleines dazuzuaddieren, dass [mm] $(x_0 [/mm] + [mm] \varepsilon)^2 [/mm] = [mm] x_0 [/mm] + A [mm] \varepsilon$ [/mm] ist (modulo [mm] $2^{r+1}$): [/mm] dann hat man anstelle einer quadratischen Gleichung eine lineare Gleichung in [mm] $\varepsilon$, [/mm] die man loesen muss.
Eine etwas andere Erklaerung: du hast eine Loesung [mm] $x_0$ [/mm] modulo [mm] $2^r$ [/mm] gegeben: es gilt also [mm] $x_0^2 \equiv [/mm] v [mm] \pmod{2^r}$. [/mm] Du kannst das [mm] $x_0^2$ [/mm] jetzt um beliebige Vielfache von [mm] $2^r$ [/mm] aendern, ohne etwas an der Gleichung zu aendern. Anders gesagt: du kannst [mm] $x_0$ [/mm] so aendern, dass sich [mm] $x_0^2$ [/mm] um Vielfache von [mm] $2^r$ [/mm] aendert. Das ist meist der Fall, wenn man [mm] $x_0$ [/mm] modulo [mm] $2^{r-k}$ [/mm] fuer kleines $k$ aendert: wie klein $k$ wirklich sein muss (damit sich [mm] $x_0^2$ [/mm] modulo [mm] $2^r$ [/mm] nicht aendert) (hier zeigt sich $k [mm] \le [/mm] 1$) und wie gross es sein muss (damit sich [mm] $x_0^2$ [/mm] modulo [mm] $2^{r+1}$ [/mm] aendert) (hier zeigt sich $k [mm] \ge [/mm] 1$) haengt immer davon ab was man fuer Gleichungen am loesen ist.
> Das erinnert mich so n bißchen an
> homogene+spezielle Lösung, wüsste aber nicht wie man das
> auf die Modulrechnung anwenden sollte......
Ich weiss nicht ob es viel bringt, es damit zu vergleichen.
> ....Und auch den Zusatz mit t = 0 oder t = 1 kann ich
> nicht wirklich einordnen.
Nun, du kannst auch $t$ ganz anders waehlen, es muss einfach eine gerade Zahl sein, die die Kongruenz [mm] $x_0 [/mm] t [mm] \equiv \frac{v - x_0^2}{2^r} \pmod{2}$ [/mm] erfuellt. Egal wie $v$ und [mm] $x_0$ [/mm] aussehen, du kannst immer $t = 0$ oder $t = 1$ waehlen, da hier modulo 2 gearbeitet wird.
LG Felix
|
|
|
|
