NS von x^4 - 12 in Z/37^2Z < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:45 Mi 29.10.2008 | | Autor: | Irmchen |
| Aufgabe | | Hat das Ploynom [mm] x^4 - 12 [/mm] eine Nullstelle in [mm] \mathbb Z / 37^2 \mathbb Z [/mm] ? Wenn ja, finden Sie eine solche! |
Hallo alle zusammen!
Ich habe hier eine Lösung, die ich leider nur ansatzweise verstehe... Ich hoffe, dass mir jemand behilflich sein kann, diese vollkommen zu verstehen.
Lösung :
Wir suchen eine Zahl [mm] y \in \mathbb Z [/mm] mit
[mm] y^4 \equiv 12 \mod 37 [/mm]
( 1. Frage: Warum nicht modulo [mm] 37^2 [/mm] ? )
Es gilt [mm] 9^4 \equiv 12 \mod 37 [/mm]
( 2. Frage: Was wurde denn jetzt mit der [mm] 9^4 [/mm] gezeigt, dass es ein Lösung gilt ? )
[mm] \Rightarrow [/mm] es ex. [mm] k \in \mathbb Z : ( 9 + k \cdot 37)^4 \equiv 12 \mod 37^2 [/mm]
( 3. Frage: Warum jetzt auf einmal [mm] 37^2 [/mm] . Warum stimmt diese Kongruenz? Ich sehe das leider nicht .... :-( )
Wir berechnen k :
[mm] ( 9 + k \cdot 37)^4 = ( 9^4 + 4 \cdot 9^3 + k \cdot 37 + 6 \cdot 9^2 k^2 37^2 + 4 \cdot 9 k^3 37^3 + k^4 37^4 ) [/mm]
[mm] \equiv 9^4 + 4 \cdot 9^3 + k \cdot 37 \mod 37^2 [/mm]
[mm] \equiv ( 12 + 37 l ) + 4 \cdot 9^3 + k \cdot 37 \mod 37^2 [/mm]
[mm] \Leftrightarrow ( 9 + k \cdot 37)^4 - 12 \equiv 37 \cdot 177 + 4 \cdot 9^3 + k \cdot 37 \mod 37^2 [/mm]
( 4. Frage: Wie bekommt man l = 177 heraus? Durch probieren ? )
[mm] \equiv 0 \mod 37^2 [/mm]
( 5. Frage : Warum gilt die folgende Äquivalent (*) ?
Weil man beide Seiten durch 37 geteilt hat ?)
(*) [mm] \Leftrightarrow 177 + 4 \cdot 9^3 k \equiv 0 \mod 37 [/mm]
[mm] \Leftrightarrow 4 \cdot 9^3 k \equiv -177 \mod 37 [/mm]
[mm] \Leftrightarrow 4 \cdot 9^3 k \equiv 8 \mod 37 [/mm]
[mm] \Leftrightarrow k \equiv ( 4 \cdot 9^3)^{-1} \cdot 8 \mod 37 [/mm]
[mm]\Leftrightarrow k \equiv ( 178)^{-1} \cdot 8 \mod 37 [/mm]
[mm]\Leftrightarrow k \equiv ( 30)^{-1} \cdot 8 \mod 37 [/mm]
[mm] \Leftrightarrow k \equiv ( 30)^{35} \cdot 8 \mod 37 [/mm]
( 5. Frage: Wie kommt ma nun auf das hoch 35 ? )
[mm] \Leftrightarrow k \equiv ( -7)^{17} \cdot 8 \mod 37 [/mm]
( 6. Frage: Und wie auf diese -7 ^17 ?)
[mm] \Leftrightarrow k \equiv 20 \mod 37 [/mm]
Wähle k = 20 [mm] \Rightarrow x = 9 + 20 \cdot 37 = 749 [/mm]
Was hat man hier für ein Verfahren verwendet?
Ich hoffe, dass mir jemand helfem kann..!
Vielen Dank!
Viele Grüße
Irmchen
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 08:04 Mo 03.11.2008 | | Autor: | statler |
Guten Morgen!
> Hat das Ploynom [mm]x^4 - 12 [/mm] eine Nullstelle in [mm]\mathbb Z / 37^2 \mathbb Z[/mm]
> ? Wenn ja, finden Sie eine solche!
> Ich habe hier eine Lösung, die ich leider nur ansatzweise
> verstehe... Ich hoffe, dass mir jemand behilflich sein
> kann, diese vollkommen zu verstehen.
>
> Lösung :
>
> Wir suchen eine Zahl [mm]y \in \mathbb Z[/mm] mit
> [mm]y^4 \equiv 12 \mod 37[/mm]
>
> ( 1. Frage: Warum nicht modulo [mm]37^2[/mm] ? )
Weil wir mit einer Näherungslösung anfangen und die dann verbessern.
> Es gilt [mm]9^4 \equiv 12 \mod 37[/mm]
>
> ( 2. Frage: Was wurde denn jetzt mit der [mm]9^4[/mm] gezeigt, dass
> es eine Lösung gibt ? )
Die [mm] 9^4 [/mm] ist unser Startwert. Wenn es eine Lösung mod [mm] 37^2 [/mm] gibt, dann ist das doch insbesondere eine Lösung mod 37. Die Existenz einer Lösung mod 37 ist eine notwendige Bedingung und hiermit erfüllt.
> [mm]\Rightarrow[/mm] es ex. [mm]k \in \mathbb Z : ( 9 + k \cdot 37)^4 \equiv 12 \mod 37^2[/mm]
> ( 3. Frage: Warum jetzt auf einmal [mm]37^2[/mm] . Warum stimmt
> diese Kongruenz? Ich sehe das leider nicht .... :-( )
Die stimmt nicht, sondern wir suchen ein k so, daß sie stimmt.
> Wir berechnen k :
> [mm]( 9 + k \cdot 37)^4 = ( 9^4 + 4 \cdot 9^3 \cdot k \cdot 37 + 6 \cdot 9^2 k^2 37^2 + 4 \cdot 9 k^3 37^3 + k^4 37^4 )[/mm]
Alle Terme mit [mm] 37^2 [/mm] solltest du weglassen, wir rechnen mod [mm] 37^2.
[/mm]
> [mm]\equiv 9^4 + 4 \cdot 9^3 \cdot k \cdot 37 \mod 37^2[/mm]
Aha! Jetzt gehen wir auf das k los!
[mm] 9^4 [/mm] + 4 [mm] \cdot 9^3 \cdot [/mm] k [mm] \cdot [/mm] 37 [mm] \equiv [/mm] 12 mod [mm] 37^2
[/mm]
formen wir um zu
[mm] (9^4 [/mm] - 12) + 4 [mm] \cdot 9^3 \cdot [/mm] k [mm] \cdot [/mm] 37 [mm] \equiv [/mm] 0 mod [mm] 37^2
[/mm]
und teilen durch 37:
177 + 2916k [mm] \equiv [/mm] 0 mod 37
29 + 30k [mm] \equiv [/mm] 0 mod 37
k [mm] \equiv [/mm] 20 mod 37
> Was hat man hier für ein Verfahren verwendet?
Newtonsches Näherungsverfahren in p-adischen Zahlkörpern
Übrigens ist 2 eine Primitivwurzel mod 37, damit kann man alle Gleichungen relativ flott lösen.
> Ich hoffe, dass mir jemand helfem kann..!
Konnte ich?
Gruß aus Harburg
Dieter
|
|
|
|
