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

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

• $6x\equiv 3\;({\text{mod}}\ 9)$
• $6x\equiv 4\;({\text{mod}}\ 9)$

Hilfreiches

Restklassen

Restklassen

Restklassen modulo $m$:

${\overline {a}}=\lbrace a+km|k\in \mathbb {Z} \rbrace _{m}$

Siehe Beispiele 74-76

Lösungsversuch (korrigiert)

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 $\equiv$ 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 $\equiv$ 3b mod m dasselbe wie a $\equiv$ 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 $\equiv$ 3b mod 3m entspricht a $\equiv$ b mod m, d.h. auch m muß dividiert werden.

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

ad a) 6x $\equiv$ 3 mod 9, 2x $\equiv$ 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 $\equiv$ 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 ... $\infty$} (für ganze Zahlen: 2 $\pm$ 3k {k = 0 ... $\infty$})

ad b) 6x $\equiv$ 4 mod 9 3x $\equiv$ 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 + $\pm$ 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