Gleichungssytem Modularithmetik

12.12.2008, 01:38

minimizer

Gleichungssytem Modularithmetik

Hallo zusammen,

ich beschäftige mich seit kurzem intensiver mit Mathe, weil es mir ziemlich Spaß macht und ich mich auf ein Studium vorbereiten möchte. Momentanes Thema ist die modulare Arithmetik, mit der ich bisher eigentlich keine Schwierigkeiten hatte. Jetzt stand in einem meiner Bücher aber folgende Übungsaufgabe, leider ohne Lösungsweg:

Lösen Sie das folgende Gleichungssystem in $\begin{eqnarray*} ~\mathbb Z_{13} \end{eqnarray*}$ :

$\begin{eqnarray*} 5x + 17y = 12 \end{eqnarray*}$

$\begin{eqnarray*} 14x + 12y = 11 \end{eqnarray*}$

Ich weiß, wie man gewöhnliche lineare Gleichungssysteme löst, und ich kann die beiden Gleichungen getrennt voneinander auch ohne Probleme für $\begin{eqnarray*} ~\mathbb Z_{13} \end{eqnarray*}$ lösen. Nur leider habe ich keine Ahnung, wie ich beides verknüpfe. Was immer ich versuche, es klappt nicht wirklich. Leider ist für diese Aufgabe kein Lösungsweg angegeben (nur die Lösung selbst, die mir aber nicht wirklich weiterhilft).

Weiß jemand, wie man generell vorgeht beim Lösen von Gleichungssystemen in modularer Arithmetik?

Danke schon im Voraus!

12.12.2008, 07:47

Auf diesen Beitrag antworten »

Da $\begin{eqnarray*} \mathbb{Z}_{13} \end{eqnarray*}$ ein Körper ist, kannst du mit üblichen Methoden (Gaussalgorithmus, etc.) das System lösen. Insbesondere die Division ist natürlich die Division in $\begin{eqnarray*} \mathbb{Z}_{13} \end{eqnarray*}$ .

Vielleicht reicht es ja schon, die Koeffizienten passend gemäß $\begin{eqnarray*} \mathbb{Z}_{13} \end{eqnarray*}$ zu reduzieren:

$\begin{eqnarray*} 5x + 4y = -1 \end{eqnarray*}$
$\begin{eqnarray*} x - y = -2 \end{eqnarray*}$

12.12.2008, 09:21

minimizer

Auf diesen Beitrag antworten »

Hallo!

Herzlichen Dank für die schnelle Antwort! Zunächst einmal muss ich mich entschuldigen, mir ist nämlich ein peinlicher Fehler unterlaufen. Gefragt war nach der Lösung in $\begin{eqnarray*} \mathbb{Z}_{27} \end{eqnarray*}$ , sorry unglücklich

. Ich habe danach noch eine Aufgabe für $\begin{eqnarray*} \mathbb{Z}_{13} \end{eqnarray*}$ gemacht und zu der fortgeschrittenen Stunde dann beim Aufschreiben beide vermischt unglücklich

.

Du konntest mir aber dennoch den entscheidenden Hinweis geben! Nämlich:

Zitat:

Insbesondere die Division ist natürlich die Division in $\begin{eqnarray*} \mathbb{Z}_{13} \end{eqnarray*}$ .

bzw.

Zitat:

Vielleicht reicht es ja schon, die Koeffizienten [...] zu reduzieren.

Den Gaussalgorithmus hatte ich versucht, und zwar folgendermaßen:

$\begin{eqnarray*} \begin{pmatrix} 5 &17 \\ 14 &12 \end{pmatrix} = \begin{pmatrix}12 \\ 11 \end{pmatrix} \end{eqnarray*}$

Da 5 und 14 teilerfremd sind, multiplizierte ich a mit 14 und b mit 5

$\begin{eqnarray*} \begin{pmatrix} 70 &238 \\ 70 &60 \end{pmatrix} = \begin{pmatrix}168 \\ 55 \end{pmatrix} \end{eqnarray*}$

Dann z.B. a - b ergibt

$\begin{eqnarray*} 178y = 113 \end{eqnarray*}$

An dieser Stelle hing ich völlig fest und machte nur noch Blödsinn. Heute Morgen aber dann der entscheidende Schritt:

$\begin{eqnarray*} 16y = 5 (mod 27) \end{eqnarray*}$

Das Inverse konnte ich dann in bekannter Weise ermitteln (y = 2), und von dort ausgehend auch x:

$\begin{eqnarray*} 5x + 17y = 12 \\ 5x + 34 = 12 \\ 5x = -22 = 5 (mod 27) \\ x = 1 \end{eqnarray*}$

Bei Tageslicht betrachtet sieht vieles doch ziemlich simple aus... danke nochmal!

Neue Frage »

Antworten »

Gleichungssytem Modularithmetik

Verwandte Themen