TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 303

Man bestimme mit Hilfe der Lösungsformel für quadratische Gleichungen alle Lösungen von $\overline{3} x^{2} + \overline{2} x + \overline{6} = \overline{0}$ über dem Körper $ℤ_{7}$ .

Hilfreiches

Es existiert ein Datei:M302.java.gz zur Suche der Restklassen-Elemente.

Große Lösungsformel

Große Lösungsformel

$a x^{2} + b x + c = 0 ⟹ x_{1, 2} = \frac{- b \pm \sqrt{b^{2} - 4 a c}}{2 a}$ .

Restklassen

Restklassen

Restklassen modulo $m$ :

$\overline{a} = {a + k m | k \in ℤ}_{m}$

Restklassenring

Restklassenring

Allgemein gilt:

Eine Restklassenring $R_{m}$ bildet einen Körper, wenn $m$ prim (ansonsten existiert i.A. kein multiplikatives Inverses).

Lösung von Baccus

Der naive Versuch, eine Lösung auf $ℤ$ zu finden, schlägt fehl: Der Wert der Diskriminante $D = b^{2} - 4 a c = 2^{2} - 4 \cdot 3 \cdot 6 = - 68 < 0$ besagt, daß keine Lösung (in M $< ℂ$ ) existiert.

Nachdem wir aber auf dem Restklassenkörper $ℤ / 7 ℤ$ operieren, kommen zwei Lösungsmöglichkeiten in Betracht:

wir verallgeimeinern die gegebenen Werte aus $ℤ_{7}$ auf $ℤ$ , lösen das Problem in $ℤ$ und spezialisieren das Ergebnis wieder auf $ℤ_{7}$ .
wir lösen das Problem vollständig in $ℤ_{7}$ , wobei wir aber für die Zwischenergebnisse immer wieder passende Restklassenwerte finden müssen.

Lösung auf Z:

Auf dem Restklassenring $ℤ / 7 ℤ$ können wir die Diskriminante in den Bereich $\geq 0$ zwingen, indem wir andere Werte aus den jeweiligen Restklassen der Angabewerte (aus $ℤ_{7}$ ) zur Lösung in $ℤ$ verwenden.

Z.B. (Werte mit o.g. Datei:M302.java.gz gefunden):

$\begin{matrix} a = 3, & b = 2 + 1 m |_{m = 7} = 9_{ℤ}, & c = 6 \end{matrix}$ :

Diskriminante $D = b^{2} - 4 a c = {\overline{2}}^{2} - 4 \cdot \overline{3} \cdot \overline{6} \overset{z . B .}{=} 9^{2} - 4 \cdot 3 \cdot 6 = 9 \geq 0 \sqrt$ Lösung existiert (in $ℝ$ ); falls die Gleichung ganzzahlig aufgeht (was sie mit den gewählten Zahlenwerten auch tut), ist die Lösung auch in $ℤ$ .

$a x^{2} + b x + c = \overline{3} x^{2} + \overline{2} x + \overline{6} \overset{z . B .}{=} 3 x^{2} + 9 x + 6 = 0 ⟹$

$x_{1, 2} = \frac{- 9 \pm \sqrt{9^{2} - 4 \cdot 3 \cdot 6}}{2 \cdot 3} \Rightarrow$

$x_{1} = \frac{- 9 + 3}{6} = - 1 \overset{z . B .}{=} (- 1 + k \cdot m)_{m = 7 \in ℙ : p r i m}^{k = 1 \in ℤ} = 6 \in {\overline{6}}_{ℤ_{7}}$

$x_{2} = \frac{- 9 - 3}{6} = - 2 = \dots \in {\overline{5}}_{ℤ_{7}}$

Lösung auf Z7:

Die Diskriminante $D = b^{2} - 4 a c = {\overline{2}}^{2} - 4 \cdot \overline{3} \cdot \overline{6} = {\overline{2}}^{2} - 4 \cdot \overline{3} \cdot \overline{6} = - 68$ ist negativ, aber in $\in {\overline{2}}_{ℤ_{7}}$ .

Also erweitern wir $D$ z.B. mit $11 m |_{m = 7}$ : $\underset{3 \in \overline{3}}{\underset{⏟}{\sqrt{\underset{= 9 \in \overline{2}}{\underset{⏟}{- 68 + 11 m |_{m = 7}}}}}}$ $= 3 \in \overline{3}$ .

Dann ist $x_{1, 2} = \frac{\overset{\in \overline{5}}{\overset{⏞}{- \overline{2}}} \pm \overset{\in \overline{3}}{\overset{⏞}{\sqrt{D}}}}{\underset{\in \overline{6}}{\underset{⏟}{2 \cdot \overline{3}}}} ⟹$

$x_{1} = \frac{\overline{5} + \overline{3} (\overset{z . B}{+} 4 m |_{m = 7})}{\overline{6}} = \overline{6}$ ,

$x_{2} = \frac{\overline{5} - \overline{3} (\overset{z . B}{+} 4 m |_{m = 7})}{\overline{6}} = \overline{5}$ .

Kontrolle der Ergebnisse auf Z7:

(Fleißaufgabe):

$x_{1} \overset{z . B .}{=} 6 \in \overline{6} : \overline{3} x_{1}^{2} + \overline{2} x_{1} + \overline{6} \overset{?}{=} \overline{0} \Rightarrow \underset{108 \in \overline{3}}{\underset{⏟}{3 \cdot 6 \cdot 6}} + \underset{12 \in \overline{5}}{\underset{⏟}{2 \cdot 6}} + \underset{\in \overline{6}}{\underset{⏟}{6}} = \underset{14 \in \overline{0}}{\underset{⏟}{\overline{3} + \overline{5} + \overline{6}}} = \overline{0} \sqrt$

$x_{2} \overset{z . B .}{=} - 2 \in \overline{5} : \overline{3} x_{2}^{2} + \overline{2} x_{2} + \overline{6} \overset{?}{=} \overline{0} \Rightarrow \underset{12 \in \overline{5}}{\underset{⏟}{3 \cdot - 2 \cdot - 2}} + \underset{- 4 \in \overline{3}}{\underset{⏟}{2 \cdot - 2}} + \underset{\in \overline{6}}{\underset{⏟}{6}} = \underset{14 \in \overline{0}}{\underset{⏟}{\overline{5} + \overline{3} + \overline{6}}} = \overline{0} \sqrt$

$x \overset{z . B .}{=} 12 \in \overline{5} : \overline{3} x^{2} + \overline{2} x + \overline{6} \overset{?}{=} \overline{0} \Rightarrow \underset{432 \in \overline{5}}{\underset{⏟}{3 \cdot 12 \cdot 12}} + \underset{24 \in \overline{3}}{\underset{⏟}{2 \cdot 12}} + \underset{\in \overline{6}}{\underset{⏟}{6}} = \underset{14 \in \overline{0}}{\underset{⏟}{\overline{5} + \overline{3} + \overline{6}}} = \overline{0} \sqrt$

$x \overset{z . B .}{=} \dots$

Baccus 01:12, 14. Jan 2007 (CET)

(Danke Hapi, Navyseal)

Lösung von Hapi

Da man mit mit Restklassen rechen kann, sollte man für b = 2 mod 7 wie folgt einsetzen: b = 9

Das ergibt dann nach der Formel (die Restklassen darf ich ja in 7-er Schritten erweitern!)

 $x_{1, 2} = \frac{- \overline{9} \pm \sqrt{{\overline{9}}^{2} - 4 * \overline{3 * 6}}}{\overline{2 * 3}} = \frac{- \overline{9} \pm \sqrt{\overline{81} - \overline{72}}}{\overline{6}} = \frac{- \overline{9} \pm \sqrt{\overline{9}}}{\overline{6}}$  =  $\frac{- \overline{9} \pm 3}{\overline{6}}$   = -2 bzw. -1.

Das Einsetzen der Werte ergibt folgende Gleichungen mit Restklassen:

$\overline{3}$ *(-1)² + $\overline{2} * (- 1) + \overline{6} = \overline{3} - (7) - \overline{2} * 1 + \overline{6} = \overline{0}$ bzw $\overline{3}$ *(-2)² + $\overline{2} * (- 2) - \overline{6} = \overline{12} - (2 * 7) - \overline{4} + \overline{6} = \overline{0}$

denn -2*7 und -1*7 sind zulässige Erweiterungen bei Modulo 7.

Hapi

Urbanek hat noch eine andere Lösungsvarieante gebracht:

$x_{1, 2} = \frac{- \overline{2} \pm \sqrt{{\overline{2}}^{2} - 4 * \overline{3 * 6}}}{\overline{2 * 3}} = \frac{- \overline{2} \pm \sqrt{\overline{4} - \overline{2}}}{\overline{6}} = \frac{- \overline{2} \pm \sqrt{\overline{2}}}{\overline{6}} = (- \overline{2} \pm \sqrt{\overline{2}}) * {\overline{6}}^{'} = (- \overline{2} \pm \sqrt{\overline{2}}) * \overline{6} = (- \overline{2} \pm \overline{3}) * \overline{6} =$

Ergebnis 1 : $\overline{1} * \overline{6} = \overline{6}$

Ergebnis 2 : $- \overline{5} * \overline{6} = - \overline{30} = \overline{5}$

Er hat statt durch Restklasse 6 dividiert mit dem Inversen davon multipliziert, was zufälligerwiese wieder 6 ist. Außerdem hat er nach jedem Rechenschritt die jeweilige Restklasse mod 7 verwendet, z.b. statt 72 nur 2, etc.