Kongruenzgleichung und euklidischer Algorithmus

12.02.2011, 18:41

tigerbine

Kongruenzgleichung und euklidischer Algorithmus

Hallo,

ich möchte gerade ein Beispiel nachvollziehen und bekomme die Brücke nicht geschlagen. In der Anleitung zur Lösung eines Systems von Kongruenzgleichungen bin ich im Teilschritt: suche $\begin{eqnarray*} k_1 \in \mathbb Z \end{eqnarray*}$ mit

$\begin{eqnarray*} 35k_1 \equiv 1 (\mod 3) \end{eqnarray*}$

Wenn man es nicht sieht, dann soll man den euklidischen Algorithmus nehmen. Das möchte ich tun. Jedoch frage ich mich gerade: wie? Der Eu-Alg. liefert den ggT zweier Zahlen. Wie bringt mich das hier denn weiter?

12.02.2011, 18:53

HAL 9000

Auf diesen Beitrag antworten »

Zur Lösung der Kongruenzgleichung $\begin{eqnarray*} ax \equiv b \bmod m \end{eqnarray*}$ :

1.Fall: $\begin{eqnarray*} a,m \end{eqnarray*}$ teilerfremd

Dann liefert der Erweiterte (!) Euklidische Algorithmus (EEA) zwei ganze Zahlen $\begin{eqnarray*} u,v \end{eqnarray*}$ mit $\begin{eqnarray*} au + mv = 1 \end{eqnarray*}$ , woraus

$\begin{eqnarray*} au \equiv 1\bmod m \end{eqnarray*}$

folgt, und daraus wiederum

$\begin{eqnarray*} aub \equiv b\bmod m \end{eqnarray*}$ ,

somit ist $\begin{eqnarray*} x \equiv ub\bmod m \end{eqnarray*}$ die eine Lösung der Ausgangskongruenz.

2.Fall: $\begin{eqnarray*} ggT(a,m) = d > 1 \end{eqnarray*}$

Später, sofern überhaupt nötig. Augenzwinkern

12.02.2011, 19:25

tigerbine

Auf diesen Beitrag antworten »

Aha. In dem Lehrbuch wird das nicht EEA genannt, sondern als Rückwärtssubstitution geführt. Nun ist die Brücke geschlagen. Dankeschön. Wink

14.02.2011, 20:16

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von tigerbine
Aha. In dem Lehrbuch wird das nicht EEA genannt, sondern als Rückwärtssubstitution geführt.

Wenn mir "Rückwärtssubstitution" das gemeint ist, was ich annehme, nämlich dass man ausgehend von der letzten Division im Euklidischen Algorithmus angewandt auf a und b mit nichtverschwindendem Rest, welcher dann den ggT d darstellt, solange "rückwärts einsetzt", bis man die gewünschte Linearkombination d=xa+yb dastehen hat, so wäre das gerade nicht der EEA, sondern bestenfalls ein heuristischer Beweis, dass man den ggT so darstellen kann...

Tatsächlich geht der EEA nicht von "unten nach oben" sondern von "oben nach unten" im Divisionsschema, wie ich das hier an einem Beispiel ausgeführt habe (bei der manuellen Durchführung des EEA arbeitet man aber tatächlich mit Tabellen)...

Neue Frage »

Antworten »

Kongruenzgleichung und euklidischer Algorithmus

Verwandte Themen