Kongruenzgleichung < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Bestimmen sie die Lösung der folgenden Kongruenzgleichung für $ x [mm] \in \IZ [/mm] $
$$ 168x [mm] \equiv [/mm] b\ mod\ 297 $$ in Abhängigkeit von $ b [mm] \in \IZ [/mm] $. |
Kann mir jemand das grundlegende Prinzip beim Lösen von Kongruenzgleichungen erklären? Ich habe sowas noch nie gemacht und das einzige Beispiel aus der Vorlesung wurde ganz erbarmungslos heruntergeleiert. Die Wikipedia-Artikel zur Kongruenz, zum Chinesischen Restsatz und zu linearen Kongruenzen habe ich zwar schon gelesen, aber konnte daraus wenig Hilfe für die Aufgabe ziehen. Gibt es da evtl andere Quellen im Internet, die das erklären? Könnte vielleicht jemand ein Beispiel vorrechnen?
Vielen Dank im Voraus.
~LG W
|
|
| |
|
Die Aufgabe enthält einen Haken: [mm] \ggT{(168;297)=3}
[/mm]
Lösung gibt es daher nur für [mm] b\equiv0\mod{3}.
[/mm]
Die Aufgabe lässt sich dann auch fassen als [mm] 56x'\equiv b'\mod{99}.
[/mm]
Wenn Du jetzt aus dem Ansatz [mm] 56a\equiv 1\mod{99} [/mm] ein a bestimmst, dann hast Du die Aufgabe schon fast gelöst.
Tipp: [mm] 56*2^5\equiv10\mod{99}
[/mm]
|
|
|
| |
|
Danke für Deine Antwort, allerdings hilft mir sie nur bedingt weiter. Den [mm] $ggT(168, 297)$ [/mm] hatte ich bereits errechnet und kam wie Du zu $ [mm] 56x\equiv [/mm] b [mm] \mod{99}$.
[/mm]
Allerdings fehlt mir nach wie vor ein Schema, wie ich allgemein mit Kongruenzgleichungen zu verfahren habe. Daher auch meine anfängliche Bitte um ein Beispiel mit Erklärung.
|
|
|
| |
|
Du findest relativ leicht [mm] 56*23\equiv1\mod{99}.
[/mm]
23 ist also in der Restklasse das inverse Element.
Folglich ist [mm] 56x'*23\equiv23*b'\mod{99} [/mm] bzw. [mm] x'\equiv23b'\mod{99}.
[/mm]
Nun bist Du fast fertig, aber eben nur fast.
|
|
|
| |
|
Ich glaube Dir ja, dass Du mir die gesamte Aufgabe vorrechnen könntest, aber ich möchte doch lediglich verstehen und erklärt kriegen, wie ich sie SELBST lösen kann. :)
Meine Frage ist nicht die nach einer LÖSUNG, sondern die nach einer VORGEHENSWEISE. Z.B. aus welchen Regeln und Sätzen ziehst Du Deine Schlüsse? Ich kann fast keinen Deiner Schritte nachvollziehen. :(
|
|
|
| |
|
Hallo Wastelander,
> Ich glaube Dir ja, dass Du mir die gesamte Aufgabe
> vorrechnen könntest, aber ich möchte doch lediglich
> verstehen und erklärt kriegen, wie ich sie SELBST lösen
> kann. :)
>
> Meine Frage ist nicht die nach einer LÖSUNG, sondern die
> nach einer VORGEHENSWEISE. Z.B
. aus welchen Regeln und
> Sätzen ziehst Du Deine Schlüsse? Ich kann fast keinen
> Deiner Schritte nachvollziehen. :(
Um die Kongruenz
[mm]56x \equiv c \ \left(99\right)[/mm]
zu lösen, hat rev erstmal das multiplikative Inverse von 56
in der Restklasse gebildet. Um dieses Inverse zu bestimmen,
wird der ![[]](/images/popup.gif) erweiterte euklidischen Algorithmus
auf die Zahlen 99 und 56 angewandt.
Daraus ergibt sich dann die Darstellung:
[mm]ggT\left(56,99\right)=s*99+t*56[/mm]
,wobei dann t das gesuchte Inverse ist.
Nun kann man die Lösung hier explizit angegeben:
Nun wende ich das auf die Kongruenz an:
[mm]56x \equiv c \ \left(99\right)[/mm]
Multipliziere beide Seiten mit t, dann erhalte ich
[mm]\left(t*56\right)*x=t*c \ \left(99\right)[/mm]
Da [mm]t*56 \equiv 1 \ \left(99\right)[/mm] ergibt sich:
[mm]x \equiv t*c \ \left(99\right)[/mm]
Gruß
MathePower
|
|
|
|
