TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 434

Aus VoWi
Zur Navigation springen Zur Suche springen

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}.

Hilfreiches[Bearbeiten]

Es existiert ein Programm-Entwurf (als Text) zur Suche der Restklassen-Elemente.
Große Lösungsformel
Große Lösungsformel[Bearbeiten]

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

Restklassen
Restklassen[Bearbeiten]

Restklassen modulo m:

\overline{a}=\lbrace a+km|k\in\mathbb{Z}\rbrace_{m}

Restklassenring
Restklassenring[Bearbeiten]

Allgemein gilt:

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

Lösung von Baccus[Bearbeiten]

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\cdot3\cdot6=-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:[Bearbeiten]

Auf dem Restklassenring \mathbb{Z}/7\mathbb{Z} können wir die Diskriminante in den Bereich \geq0 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\cdot3\cdot6=9\geq0\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\cdot3\cdot6}}{2\cdot3}\Rightarrow

x_1=\frac{-9+3}{6}=-1\overset{z.B.}{=}(-1+k\cdot m)^{k=1\in\mathbb{Z}}_{m=7\in\mathbb{P}:prim}=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:[Bearbeiten]

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}{+}4m|_{m=7})}{\overline{6}}=
\overline{5}.

Kontrolle der Ergebnisse auf Z7:[Bearbeiten]

(Fleißaufgabe):

  • x_1\overset{z.B.}{=}6\in\overline{6}:\quad\overline{3}x^2_1+\overline{2}x_1+\overline{6}\overset{?}{=}\overline{0}\Rightarrow
\quad\underset{108\in\overline{3}}{\underbrace{3\cdot6\cdot6}}+
  \underset{12\in\overline{5}}{\underbrace{2\cdot6}}+
  \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\cdot12\cdot12}}+
  \underset{24\in\overline{3}}{\underbrace{2\cdot12}}+
  \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[Bearbeiten]

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}\pm3}{\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[Bearbeiten]

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[Bearbeiten]

Wikipädia:

Ähnliche Beispiele: