TU Wien:Mathematik 1 UE (diverse)/Übungen WS07/Beispiel 58

Aus VoWi
Zur Navigation springen Zur Suche springen

Lösen Sie die folgenden Kongruenzen (d.h. Gleichungen in Restklassen) bzw. beweisen Sie die Unlösbarkeit:


Hilfreiches[Bearbeiten | Quelltext bearbeiten]

Restklassen
Restklassen[Bearbeiten | Quelltext bearbeiten]

Restklassen modulo :

Siehe Beispiele 74-76

Lösungsversuch (korrigiert)[Bearbeiten | Quelltext bearbeiten]

Rechnen mit Kongruenzen


Allgemeines:

Modulo teilt Werte in Restklassen durch Division mit dem Mod-Wert e, d.h. alle Elemente derselben Restklasse haben bei der Division durch m (Modulo) denselben Rest.

a b mod m bedeutet daher bei Bestehen der Kongruenz daß a/m und b/m denselben Rest haben. Daraus folgt, daß m | (a-b) gilt und somit m den Term (a-b) ohne Rest teilt (sonst nicht kongruent!).

Weiters bedeutet 3a 3b mod m dasselbe wie a b mod m, man kann also die linke Seite des Ausdrucks um den gemeinsamen Teiler kürzen, wenn auf der rechten Seite m nicht teilbar ist.

Ist m aber ebenfalls teilbar, so lautet die Rechenregel 3a 3b mod 3m entspricht a b mod m, d.h. auch m muß dividiert werden.

Eine Kongruenz der Form ax b ist genau dann lösbar, wenn der ggT (a, m ) die Zahl b teilt.


ad a) 6x 3 mod 9, 2x 1 mod 3

Es gibt eine Lösung denn der ggt von 6x und 9 ist 3, 3 teilt aber 3!

Denn 6*2 = 12 3 mod 9

Allgemein: x = c + m*k, für alle k (1..unendlich) aus den natürliche Zahlen N

In diesem Fall: x = 2 + 3k {k = 0 ... } (für ganze Zahlen: 2 3k {k = 0 ... })


ad b) 6x 4 mod 9 3x 2 mod 9

Es gibt keine Lösung, da der ggt von 6x und 9 ist 3, 3 teilt nicht 4, daher keine Lösung!


Hapi


Aber du darfst nicht vergessen, dass es für die ganzen Zahlen und nicht nur für die natürlichen Zahlen verlangt. Außerdem passt deine Lösung nicht, da du möglichkeiten auslässt!!

2+3k im positiven Bereich und -2+3k im negativen Bereich

Babs


Danke Babs für den Hinweis, in dem Fall ist 3 statt 9 zu verwenden und das mit negativen Zahlen wäre auch korrekt, aber in der Formel drüber steht natürliche Zahlen.

Für ganze Zahlen hättest du recht, da müßte dann statt + stehen. Habs schon ausgebessert. War da wohl etwas schlampig, aber nobody is perfect. Aber es wäre in Z dann 2 - 3k, nicht -2 + 3k.

Hapi


Wir Rechnen in Restklassen zu Z_9, da ist 2 - 3k afaik keine Lösung, da Z_9={[0], [1], [2], ....[8]}, 2-3k würde bedeuten dass z.B. 2 und 5 in der gleiche Restklasse sind, was nicht der Fall ist. Lösungen sind [2], [5], [8] Element Z_9, oder halt {i+3k | i=2,5,8 und k Element Z}.

Lg, AXEL.



Datei:TU Wien-Algebra und Diskrete Mathematik UE (diverse) - kongruenzen.pdf