Kongruenzen lösen < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Lösen Sie das Kongruenzensystem:
$x [mm] \equiv [/mm] 10$ (mod 18)
$x [mm] \equiv [/mm] 3$ (mod 5)
$x [mm] \equiv [/mm] 2$ (mod 4)
$x [mm] \equiv [/mm] 1$ (mod 3) |
moin,
Wir haben in der Vorlesung grad solche feinen Systeme und ein paar Verfahren kennengelernt, um sie zu lösen (also eine einzige Kongruenz draus zu basteln).
Der chinesische Restsatz ist ganz fein für manche Beweise und um aus einer Kongruenz (mod a*b) eine Kongruenz (mod a) und eine (mod b) zu zaubern, aber um wie hier einzelne zusammenzufassen ist der Rechenaufwand zumindest bei der Version die wir hatten viel zu groß.
Als nächstes hatten wir ein Verfahren, das ebenfalls erstmal teilerfremd macht und dann mit dem ggT arbeitet.
Auch wenn ich das noch nicht ganz verstanden hab so scheint es doch recht kompliziert zu sein, da es für diesen Fall schon 4 komplette erweiterte euklidische Algorithmen bräuchte.
Ich hab dieses System gelöst, indem ich erstmal festgestellt hab:
$x [mm] \equiv [/mm] a$ (mod n) und $x [mm] \equiv [/mm] a$ (mod m) [mm] $\gdw [/mm] x [mm] \equiv [/mm] a$ (mod kgV(m,n)) - ich hoffe doch das stimmt?^^
Da sich die letzten drei alle als -2 schreiben lassen gibt das also erstmal $x [mm] \equiv [/mm] -2$ (mod 60) und dann zusammen mit der 18 $x [mm] \equiv [/mm] 118$ (mod 180).
(Auch im zweiten Fall wieder passende Vertreter für die Restklasse finden).
Das Problem hierbei ist, dass es in diesem Fall zwar recht schnell geht, aber doch irgendwo mehr Ausprobieren als sonst etwas ist und unter Umständen irgendwann gnadenlos versagen könnte; spätestens wenn sich irgendwo in dem System ein Widerspruch verbirgt...
Deshalb würde ich von euch Profis gern mal wissen:
Wie geht ihr an so eine Aufgabe rann?
Gibt es eine besonders elegante/einfache Methode?
Taugt mein Weg etwas?
Gibt es Fälle, in denen eine bestimmte Vorgehensweise zu bevorzugen ist (woran erkennt man die)?
thx und MfG
Schadow
|
|
| |
|
Hallo Schadow,
es gibt den allgemeinen Weg; der ist halt immer etwas mühsam, funktioniert dafür sicher...
Ansonsten hast Du die Aufgabe doch geschickt gelöst.
Ich wäre trotzdem ein bisschen anders vorgegangen. Die letzte Kongruenz [mm] \mod{3} [/mm] ist ja vollkommen überflüssig, weil sie in der ersten bereits enthalten ist. Damit ist man schnell bei [mm] x\equiv 10\mod{18}\ \wedge\ 18\mod{20} [/mm] und von da dann hier zu Fuß bei Deiner Lösung, oder wenn die Zahlen größer wären, eben über die Anwendung der allgemeinen Methode.
Mit anderen Worten: es lohnt sich immer, nach Abkürzungen Ausschau zu halten.
Grüße
reverend
|
|
|
|
