Blatt 5, Nachtrag

Aufgabe 2

Zunächst einmal lösen wir die Kongruenz modulo \(7\). Da können wir sofort zwei Lösungen erraten: \(3\) und \(4\). Diese können wir nun sukzessive mithilfe des Newton-Verfahrens liften. Wir schreiben \(i_n(a)\) für einen (beliebigen) Repräsentanten von \(a^{-1}\bmod 7^n\).

• Sei \(x_1 = 3\).
• \(x_1 - (x_1^2-2)\cdot i_1(2x_1) \equiv 3 - (9-2)\cdot i_1(6) \equiv 3-7\cdot (-1) \equiv 10\bmod 7^2\), setze also \(x_1:=10\).
• \(x_2 - (x_2^2-2)\cdot i_2(2x_2) \equiv\ldots\equiv 108\bmod 7^3\), setze \(x_3:=108\)
• \(x_3 - (x_3^2-2)\cdot i_3(2x_3) \equiv\ldots\equiv 2166\bmod 7^3\), setze \(x_4:=2166\)

und so weiter. Entsprechend könnten wir natürlich auch mit \(x_1=4\) anfangen. Auf diese Weise könnten wir die andere Lösung modulo \(7^{100}\) bestimmen.

Die Berechnung ist zu aufwendig, um sie per Hand durchzuführen. Siehe auch [Sage-Programm]({{< ref "post/sose16-zt-05.md#aufgabe-2" >}}).