TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 442

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 $\mathbb {Z} _{7}$.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches

Es existiert ein Programm-Entwurf (als Text) zur Suche der Restklassen-Elemente.

Große Lösungsformel

Große Lösungsformel

$ax^{2}+bx+c=0\quad \Longrightarrow \quad x_{1,2}={\frac {-b\pm {\sqrt {b^{2}-4ac}}}{2a}}$.

Restklassen

Restklassen

Restklassen modulo $m$:

${\overline {a}}=\lbrace a+km|k\in \mathbb {Z} \rbrace _{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 $\mathbb {Z}$ zu finden, schlägt fehl: Der Wert der Diskriminante $D=b^{2}-4ac=2^{2}-4\cdot 3\cdot 6=-68<0$ besagt, daß keine Lösung (in M $<\mathbb {C}$) existiert.

Nachdem wir aber auf dem Restklassenkörper $\mathbb {Z} /7\mathbb {Z}$ operieren, kommen zwei Lösungsmöglichkeiten in Betracht:

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

Lösung auf Z:

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

Z.B. (Werte mit o.g. Java-Programm; gefunden):

${\begin{array}{lll}a=3,&b=2+1m|_{m=7}=9_{\mathbb {Z} },&c=6\end{array}}$:

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

$ax^{2}+bx+c={\overline {3}}x^{2}+{\overline {2}}x+{\overline {6}}{\overset {z.B.}{=}}3x^{2}+9x+6=0\quad \Longrightarrow$

$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 \mathbb {P} :prim}^{k=1\in \mathbb {Z} }=6\quad \in {\overline {6}}_{\mathbb {Z} _{7}}$

$x_{2}={\frac {-9-3}{6}}=-2=\cdots \quad \in {\overline {5}}_{\mathbb {Z} _{7}}$

Lösung auf Z7:

Die Diskriminante $D=b^{2}-4ac={\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}}_{\mathbb {Z} _{7}}$.

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

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

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

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

Kontrolle der Ergebnisse auf Z7:

(Fleißaufgabe):

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

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

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

• $x{\overset {z.B.}{=}}\cdots$

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!)

$\quad 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:

$\quad 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.

Hapi

Lösung von zool

Das die Inverse Restklasse von -6 wieder 6 ist kann ich mir nicht vorstellen. Das inverse einer Restklasse wird wie folgt errechnet:

a*b+m*k=1

In diesen Fall ist b=-6 und m = 7, schaut dann so aus:

1*(-6)+7*1=1

daraus folgt die Inverse Restklasse von -6 ist 1! Bis dorthin passt die Rechnung aber.

$=(-{\overline {2}}\pm {\sqrt {\overline {2}}})*{\overline {1}}'=(-{\overline {2}}\pm {\sqrt {\overline {2}}})*{\overline {1}}=(-{\overline {2}}\pm {\overline {3}})*{\overline {1}}=$

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

Ergebnis 2 : $-{\overline {5}}*{\overline {1}}=-{\overline {5}}={\overline {3}}$

Inverse Restklasse von -5:

3*(-5)+7*2=1 => 3

--Zool 13:57, 1. Feb. 2009 (UTC)

Links

• Java-Programm-Entwurf;
• Diskussion im Informatik-Forum

Wikipädia:

• Quadratische Gleichung
• Restklassenkörper
• Restklassenring
• Restklassen
• Körper

Ähnliche Beispiele:

• Beispiel 310
• Beispiel 312