TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 65

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:

Dieses Beispiel ist als solved markiert. Ist dies falsch oder ungenau? Aktualisiere den Lösungsstatus (Details: Vorlage:Beispiel)


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. beide Werte haben bei der Division durch den Faktor 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 | (b-c) gilt und somit m den Term (b-c) 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 c 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.

Lösungsversuch (von Friday)[Bearbeiten | Quelltext bearbeiten]

a)

6x 3 mod 9

6x = 3 + 9k

2x = 1 + 3k

x = (1+3k)/2

für k = 1:

x = (1+3)/2 = 2

2 ist eine ganze Zahl und somit die Lösung

b)

6x 4 mod 9

6x = 4 + 9k

6x = 4 + 9k

x = (4 + 9k)/6

für k = 1:

x = (4 + 9)/3 = 13/6 = 2.16..

2.16.. ist keine ganze Zahl und somit ist die Konkruzenz unlösbar.