Lineare Kongruenzen mit dem EEA lösen

17.07.2014, 18:47

MontyBurns

Lineare Kongruenzen mit dem EEA lösen

Meine Frage:
Hi

ich weiss das schon oft fragen zu diesem thema beantwortet wurden und damit hab ich mich intensiv beschäftigt, aber ich komme mit meine aufgabe nicht weiter

ich habe zwei kongruenzen in der form $\begin{eqnarray*} ax \equiv b \pmod{m} \end{eqnarray*}$
das x würd ich gern mit dem erweiterten euklidschen algorithmus herausfinden

Meine Ideen:
aufgabenstellung
$\begin{eqnarray*} 3x \equiv 11 \pmod{23} \end{eqnarray*}$
$\begin{eqnarray*} 7x \equiv 19 \pmod{53} \end{eqnarray*}$
entspricht
$\begin{eqnarray*} 3x = 23k + 11 | \cdot 7 \end{eqnarray*}$
$\begin{eqnarray*} 7x = 53m + 19 | \cdot 3 \end{eqnarray*}$

$\begin{eqnarray*} 21x = 161k + 77 \end{eqnarray*}$
$\begin{eqnarray*} 21x = 159m + 57 \end{eqnarray*}$

in eine lineare diophantische Gleichung umformen
$\begin{eqnarray*} 161k+77 = 159m +57 \end{eqnarray*}$
$\begin{eqnarray*} 161k - 159m = -20 \end{eqnarray*}$

Erweiterten Euklidschen Algorithmus ausführen (hab ich jetzt nicht hin geschrieben)
$\begin{eqnarray*} 161\cdot(-79) + 159\cdot80 = 1 |\cdot (-20) \end{eqnarray*}$
$\begin{eqnarray*} 161\cdot(-79)\cdot(-20) + 159\cdot 80 \cdot(-20) = -20 \end{eqnarray*}$
$\begin{eqnarray*} 161\cdot 1580 + 159\cdot (-1600) = -20 \end{eqnarray*}$
$\begin{eqnarray*} 161\cdot 1580 - 159\cdot 1600 = -20 \end{eqnarray*}$

also ist: $\begin{eqnarray*} k=1580 \end{eqnarray*}$ und $\begin{eqnarray*} m=1600 \end{eqnarray*}$

und nun? wi bekomm ich daraus jetzt x? wär super wenn mir jemand nen tipp geben könnte

gruss

MontyBurns

17.07.2014, 20:16

ralfkannenberg

Auf diesen Beitrag antworten »

RE: Lineare Kongruenzen mit dem EEA lösen
Hallo Monty,

setze k=1580 und m=1600 doch einfach hier ein:

Zitat:

Original von MontyBurns

$\begin{eqnarray*} 3x = 23k + 11 \end{eqnarray*}$

und mache hier die Probe:

Zitat:

Original von MontyBurns

$\begin{eqnarray*} 7x = 53m + 19 \end{eqnarray*}$

Freundliche Grüsse, Ralf

17.07.2014, 21:09

MontyBurns

Auf diesen Beitrag antworten »

ja. wenn ich mein k einsetze bekomme ich $\begin{eqnarray*} x=12117 \end{eqnarray*}$ raus. wenn ich das in die andere gleichung einsetze erhalte ich mein errechnetes m.

was ich aber suche ist das kleinste $\begin{eqnarray*} x \in \mathbb{Z} \end{eqnarray*}$
laut wolfram alpha müsste sowas raus kommen: $\begin{eqnarray*} k= 159n+149, \ m=161n+151, \ n\in \mathbb{Z} \end{eqnarray*}$

tut mir leid das ich das nicht in meine frage gepackt hab

17.07.2014, 23:12

ralfkannenberg

Auf diesen Beitrag antworten »

Zitat:

Original von MontyBurns

was ich aber suche ist das kleinste $\begin{eqnarray*} x \in \mathbb{Z} \end{eqnarray*}$

Hallo Monty,

ich verstehe Deinen Ansatz immer noch nicht.

Du hast oben folgendes geschrieben:

Zitat:

Original von MontyBurns

$\begin{eqnarray*} 21x = 161k + 77 \end{eqnarray*}$
$\begin{eqnarray*} 21x = 159m + 57 \end{eqnarray*}$

Wenn Du nun diese beiden Gleichungen subtrahierst, so "fliegt" das x heraus, d.h. alles was Du hinterher machst, gilt für alle x.

Ist das wirklich das, worauf Du hinaus möchtest ?

Freundliche Grüsse, Ralf

18.07.2014, 13:51

MontyBurns

Auf diesen Beitrag antworten »

also $\begin{eqnarray*} x=12117 \end{eqnarray*}$ is ja nur eine lösung. ich suche aber das kleinste $\begin{eqnarray*} x \in \mathbb{Z} \end{eqnarray*}$ für das gilt:
$\begin{eqnarray*} 3x \equiv 11 \pmod{23} \end{eqnarray*}$
$\begin{eqnarray*} 7x \equiv 19 \pmod{53} \end{eqnarray*}$
dieser schritt fehlt mir noch

18.07.2014, 14:49

ralfkannenberg

Auf diesen Beitrag antworten »

Zitat:

Original von MontyBurns
also $\begin{eqnarray*} x=12117 \end{eqnarray*}$ is ja nur eine lösung. ich suche aber das kleinste $\begin{eqnarray*} x \in \mathbb{Z} \end{eqnarray*}$ für das gilt:
$\begin{eqnarray*} 3x \equiv 11 \pmod{23} \end{eqnarray*}$
$\begin{eqnarray*} 7x \equiv 19 \pmod{53} \end{eqnarray*}$
dieser schritt fehlt mir noch

Hallo Monty,

vielleicht mache ich jetzt einen Überlegungsfehler, aber ich hatte Deinen Ansatz so verstanden, dass man zu jedem beliebigen x ein k und ein m finden kann, welches Deine Aufgabe löst. Insbesondere hast Du ja auch angegeben, wie man das berechnen kann.

Somit gibt es irgendwie kein "kleinstes" x.

Einverstanden ?

Freundliche Grüsse, Ralf

18.07.2014, 15:03

Captain Kirk

Auf diesen Beitrag antworten »

@MontyBurns:
Mache dir klar, dass mit x auch x-23*53 bzw. x+23*53 Lösungen sind.
(Im Endeffekt wird hier eine Restklasse berechnet und zwar modulo 23*53).
Dann wäre aber noch zu klären was du unter kleinstes $\begin{eqnarray*} x \in \mathbb{Z} \end{eqnarray*}$ verstehst. Betragsmäßig? Oder positiv?

18.07.2014, 15:21

ralfkannenberg

Auf diesen Beitrag antworten »

Zitat:

Original von Captain Kirk
@MontyBurns:
Mache dir klar, dass mit x auch x-23*53 bzw. x+23*53 Lösungen sind.
(Im Endeffekt wird hier eine Restklasse berechnet und zwar modulo 23*53).
Dann wäre aber noch zu klären was du unter kleinstes $\begin{eqnarray*} x \in \mathbb{Z} \end{eqnarray*}$ verstehst. Betragsmäßig? Oder positiv?

Hallo Captain Kirk,

aufgrund diverser Unstimmigkeiten mit vermutlich massgeblichen Personen dieses Forums werde ich keine weiteren Beiträge mehr leisten. Ich wäre also froh, wenn Du die "Helferrolle" für Monty übernehmen könntest.

Persönlich nochmals herzlichen Dank für Deinen Link betreffend des Assoziativgesetzes.

Freundliche Grüsse, Ralf

18.07.2014, 16:08

MontyBurns

Auf diesen Beitrag antworten »

super! habs jetzt gelöst. danke ralfkannenberg und Captain Kirk

hier mein rechenweg:
$\begin{eqnarray*} 3x \equiv 11 \pmod{23} \end{eqnarray*}$
$\begin{eqnarray*} 7x \equiv 19 \pmod{53} \end{eqnarray*}$

entspricht

$\begin{eqnarray*} 3x = 23k + 11 \ | \ \cdot 7 \end{eqnarray*}$
$\begin{eqnarray*} 7x = 53m + 19 \ | \ \cdot 3 \end{eqnarray*}$

$\begin{eqnarray*} 21x = 161k + 77 \end{eqnarray*}$
$\begin{eqnarray*} 21x = 159m + 57 \end{eqnarray*}$

in eine lineare diophantische Gleichung umformen

$\begin{eqnarray*} 161k+77 = 159m +57 \end{eqnarray*}$
$\begin{eqnarray*} 161k - 159m = -20 \end{eqnarray*}$

Erweiterten Euklidschen Algorithmus ausführen (mach ich jetzt nicht hier).
Das Ergebniss ist $\begin{eqnarray*} k=-79 \end{eqnarray*}$ und $\begin{eqnarray*} m=80 \end{eqnarray*}$ .
Da die werte für eine gleichung $\begin{eqnarray*} ax +by = ggt(a,b) \end{eqnarray*}$ stimmen, muss man sie noch auf die obige gleichung umrechnen. Dafür diesese werte in die Diophantische Gleichung einsetzen.

$\begin{eqnarray*} 161\cdot(-79) + 159\cdot80 = 1 \ | \ \cdot (-20) \end{eqnarray*}$
$\begin{eqnarray*} 161\cdot(-79)\cdot(-20) + 159\cdot 80 \cdot(-20) = -20 \end{eqnarray*}$
$\begin{eqnarray*} 161\cdot 1580 + 159\cdot (-1600) = -20 \end{eqnarray*}$
$\begin{eqnarray*} 161\cdot 1580 - 159\cdot 1600 = -20 \end{eqnarray*}$

also ist: $\begin{eqnarray*} k=1580 \end{eqnarray*}$ und $\begin{eqnarray*} m=1600 \end{eqnarray*}$

$\begin{eqnarray*} k \end{eqnarray*}$ in die ausgangsgleichung einsetzen

$\begin{eqnarray*} 21x = 161k + 77 \end{eqnarray*}$
$\begin{eqnarray*} 21x = 161 \cdot 1580 + 77 \end{eqnarray*}$
$\begin{eqnarray*} 21x = 254380 + 77 \end{eqnarray*}$
$\begin{eqnarray*} 21x = 254457 | \div 21 \end{eqnarray*}$
$\begin{eqnarray*} x = 12117 \end{eqnarray*}$

das kleinste positive $\begin{eqnarray*} x \in \mathbb{Z} \end{eqnarray*}$ herausfinden

$\begin{eqnarray*} x = 12117 \bmod{23 \cdot 53} \end{eqnarray*}$
$\begin{eqnarray*} x = 12117 \bmod{1219} \end{eqnarray*}$
$\begin{eqnarray*} x = 1146 \end{eqnarray*}$

damit ist $\begin{eqnarray*} x = 1146 \end{eqnarray*}$ das kleinste positive $\begin{eqnarray*} x \in \mathbb{Z} \end{eqnarray*}$ die die simultane Kongruenz oben erfüllt.
Allgemeiner kann man sagen das die lösungen diese form haben müssen $\begin{eqnarray*} x= 1219\cdot n +1146 \ | \ n \in \mathbb{N}_0 \end{eqnarray*}$

Neue Frage »

Antworten »

Lineare Kongruenzen mit dem EEA lösen

Verwandte Themen