0 Daumen
330 Aufrufe

Aufgabe:

Lineare Kongruenz 91x ≡ 84 (mod 147) lösen:


Problem/Ansatz:

Der ggT(91, 147) = 7 | 84 ⇒ Lösbar

Somit gibt es ja 7 inkongruente Lösungen mod 147, die sich um 147/7 = 21 unterscheiden.

91x ≡ 84 (mod 147) / 7 = 13x ≡ 12 (mod 21)

Jetzt müsste die Aufgabe mit dem EEA (erweiterter Euklidischer Algorithmus) lösbar sein - ich versteh aber noch nicht Prinzip bzw. wie ich durch die Anwendung zur Lösung komme.

Avatar von

3 Antworten

+2 Daumen
 
Beste Antwort

Ich ergänze mal diese Antwort, da bisher keiner auf deine Frage eingegangen ist.


Bisher hast du die gegebene Kongruenz äquivalent umgeformt auf

\(13x \equiv_{21} 12\)

Nun möchtest du diese Kongruenz mit Hilfe des EEA lösen.

Der EEA wird benutzt, um eine Zahl g zu finden, so dass

\(13g \equiv_{21} 1\).

Es wird also das multiplikative Inverse von 13 modulo 21 gesucht.

Da ggT(13,21) = 1, gibt es laut Lemma von Bézout Zahlen g,h, so dass

\(13g + 21h = 1 \Leftrightarrow 13g \equiv_{21} 1 \Leftrightarrow g \equiv_{21} 13^{-1}\).

Genau hier kommt der EEA ins Spiel, denn der EA liefert zunächst einen Satz von Gleichungen, die den ggT(13,21)=1 liefern.

\(\begin{array}{rcl} 21 & = & 13 + 8 \\ 13 & = & 8 + 5 \\ 8 & = & 5 + 3 \\ 5 & = & 3 + 2 \\ 3 & = & 2 + \boxed{1} \end{array}\)

Der EEA beinhaltet nun das rückwärts Auflösen dieses Satzes von Gleichungen, so dass du am Ende eine Gleichung der Form

\(13g + 21h = 1\) erhältst:

\(\begin{array}{rclcl} \boxed{1} & = & 3 - 2  &&\\  & = & 3 - (5-3) &=& -5 +2\cdot 3 \\  & = & -5 + 2\cdot (8-5)& =& 2\cdot 8 - 3\cdot 5 \\  & = & 2\cdot 8 - 3\cdot (13-8) & = & -3\cdot 13 + 5\cdot 8\\  & = & -3\cdot 13 + 5\cdot (21-13) & = & \boxed{5\cdot 21 {\color{blue}{-8}} \cdot 13}\end{array}\)

Damit haben wir

\(-8\equiv_{21}13^{-1}\).

Also

\(13x \equiv_{21} 12 \Leftrightarrow \)

\(x \equiv_{21} -8\cdot 13 x \equiv_{21}  -8 \cdot 12 \equiv_{21} -96 \equiv_{21} 9\)

Die Lösung der Kongruenz ist also

\(\boxed{x \equiv_{21} 9}\).

Avatar von 10 k

Vielen Dank für deine Erklärung - hilft mir sehr fürs Verständnis ☺

Eine Frage hätt ich noch:

Ich sehe gerade nicht, wie ich von der -96 auf das Ergebnis 9 komme? ☺

-96 = -105 + 9

Super - danke dir

105 ist ja ein vielfaches von 13 vermindert um 12:

Wenn ich das gezeigte Prinzip nun auf ein anderes Beispiel (3x ≡ 17 (mod 29)) anwende, verstehe ich's immer noch nicht ganz!

Woher weiß ich genau, dass ich die -105 nehmen muss (zu dem Zeitpunkt kenne ich das Ergebnis 9 ja noch nicht)?

Gedanklich häng ich da ☺

Der Modul ist doch 21. Also suchst du nach Vielfachen von 21.

-96 = -5×21 +9

+1 Daumen

91x ≡ 84 (mod 147)

<=> 91x-84 = k*147  | :7

<=> 13x-12=k*21

Das geht auch "zu Fuß"

Bei den Vielfachen von 13 sind z,B.

26,39,52,65,78,91,104,117,...

vermindert um 12 also

14,27,40,53,66,79,92,105

und 105=5*21.

Also ist 9 eine Lösung; denn 9*13=117.

Und 117 -12 =105 = 5*21.

Avatar von 287 k 🚀

Grundsätzlich verstehe ich das schon mal.

Ich würd trotzdem wirklich gerne wissen, wie ich das mit dem EEA sauber aufschreibe um ein multiplikatives Invers c zu finden. Der Anfang wäre ja glaub ich:

21=13*1+8

13=12*1+1

12=1*12+0

Somit wäre dann doch

x ≡ c*12 (mod 21) und die Lösung (c*12)+k*21  k∈ℤ


Oder anders gesagt, muss ich schlussendlich die 7 Lösungen exakt bestimmen - wie das geht ist mir immer noch nicht klar?

0 Daumen

Hallo

es geht viel schneller, wenn man weiss 13^2=169=8*21+1

lul

Avatar von 106 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community