Lösung einer Kongruenz < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hi Leute,
leider hänge ich bei folgender Aufgabe ein wenig fest. Vielleicht kann mir von euch jemand etwas weiter helfen. Vielen Dank schon mal im Voraus!
Löse die Kongruenz [mm] x^{2} \equiv [/mm] 5 mod [mm] 11^{n}
[/mm]
für n = 1,2,3,4,5,6,7
Nun mit Hilfe von Exel habe ich einen interessanten Zusammenhang herausgefunden:
Bei [mm] 11^{1} [/mm] lautet die Lösung:
4, 7, 15, 18, 26, ...
Dabei gilt:
(4 + 7)/11 = 1
(7 + 15)/11 = 2
(15 + 18)/11 = 3
(18 + 26)/11 = 4
usw.
Die nächste Lösung berechnet sich duch 5 * 11 (55) - 26 = 29.
Bei [mm] 11^{2} [/mm] = 121 lautet die Lösung:
48, 73, 169, 194, ...
Dabei gilt:
(48 + 73)/121 = 1
(73 + 169)/121 = 2
(169 + 194)/121 = 3
Auch hier lässt sich die nächste Lösung wie oben berechnen.
Bei [mm] 11^{3} [/mm] = 1331 lautet die Lösung:
73, 1258, 1404, 2589, ...
Hat man erst mal eine Lösung, so lassen sich die restlichen Lösungen leicht berechnen.
Mein Problem:
1. Wie komme ich zur ersten Lösung bei [mm] 11^{4} [/mm] usw.?
2. Wie sollte ich an so eine Aufgabe rangehen, wenn ich kein Exel zur Verfügung habe (Klausur)?
3. Wie könnte eine Lösung ordentlich formuliert ausehen (In Klausur)?
Gruß
Prof.
PS: hoffentlich überstehe ich diese Klausur!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:11 Fr 05.01.2007 | | Autor: | felixf |
Hallo Prof!
> leider hänge ich bei folgender Aufgabe ein wenig fest.
> Vielleicht kann mir von euch jemand etwas weiter helfen.
> Vielen Dank schon mal im Voraus!
>
> Löse die Kongruenz [mm]x^{2} \equiv[/mm] 5 mod [mm]11^{n}[/mm]
>
> für n = 1,2,3,4,5,6,7
Dazu hattet ihr doch sicher was in der Vorlesung? Eine Moeglichkeit sowas zu machen, ist ueber das Henselsche Lemma zu gehen (Newtonverfahren): Man betrachtet das Polynom $p := [mm] x^2 [/mm] - 5$ und findet Loesungen modulo 11. Daraus erhaelt man im ersten Iterationsschritt Loesungen modulo [mm] $11^2$, [/mm] beim zweiten Schritt Loesungen modulo [mm] $11^3$, [/mm] etc.
Hattet ihr das Verfahren oder so etwas in die Richtung? Wenn nicht, sag Bescheid.
> Nun mit Hilfe von Exel habe ich einen interessanten
> Zusammenhang herausgefunden:
>
> Bei [mm]11^{1}[/mm] lautet die Lösung:
> 4, 7, 15, 18, 26, ...
> Dabei gilt:
> (4 + 7)/11 = 1
Das ist nicht sonderlich ueberraschend :) Es ist ja [mm] $x^2 [/mm] - 5 [mm] \equiv [/mm] (x - 4) (x - 7) = [mm] x^2 [/mm] - (4 + 7) x + 4 [mm] \cdot [/mm] 7 [mm] \pmod{11}$, [/mm] womit $4 + 7$ durch 11 teilbar sein muss. Und wenn man nun zu einem 11 hinzuaddiert, erhoeht sich der Quotient um 1. Und wenn man zum naechsten dann auch 11 hinzuaddiert, erhoeht er sich wieder. Und so weiter.
> (7 + 15)/11 = 2
> (15 + 18)/11 = 3
> (18 + 26)/11 = 4
> usw.
>
> Die nächste Lösung berechnet sich duch 5 * 11 (55) - 26 =
> 29.
Oder allgemeiner: Die Loesungen sind gerade alle Zahlen der Form $4 + 11 n$, $7 + 11 m$ mit $n, m [mm] \in \IZ$.
[/mm]
> Mein Problem:
> 1. Wie komme ich zur ersten Lösung bei [mm]11^{4}[/mm] usw.?
Newtonverfahren (siehe oben).
> 2. Wie sollte ich an so eine Aufgabe rangehen, wenn ich
> kein Exel zur Verfügung habe (Klausur)?
Hast du einen Taschenrechner? Dann sollte das kein Problem sein. Ohne Taschenrechner muss man schon etwas mehr Kopfrechnen... Mit dem Newtonverfahren geht es allerdings immer noch vergleichsweise schnell.
> 3. Wie könnte eine Lösung ordentlich formuliert ausehen
> (In Klausur)?
Durch ausprobieren: $x = 4$ und $x = 7$ sind Loesungen von [mm] $x^2 \equiv [/mm] 5 [mm] \pmod{11}$. [/mm] Also sind alle Loesungen gegeben durch $4 + n 11$ und $7 + m 11$ mit $n, m [mm] \in \IZ$.
[/mm]
...und dann kommt halt die Begruendung fuer das verwendete Verfahren...
LG Felix
|
|
|
|
