TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 74
Lösen Sie die folgenden Kongruenzen (d.h. Gleichungen in Restklassen) bzw. beweisen Sie die Unlösbarkeit:
Hilfreiches[Bearbeiten | Quelltext bearbeiten]
Restklassen[Bearbeiten | Quelltext bearbeiten]
Restklassen modulo :
Siehe Beispiele 74-76
Lösungsversuch[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) 8x 4 mod 16, 2x 1 mod 4
Es gibt keine Lösung, da b < als a ist, b kann aber kein Bruch sein!
Oder etwas mehr mathematisch: der ggt von 8x und 16 ist 8, 8 teilt nicht 4, daher keine Lösung!
ad b) 8x 4 mod 15, 2x 1 mod 15
D.h. es gibt eine Lösung denn b teilt ax, hat aber keinen ggt mit c (15)
Denn 8*8 = 64 4 mod 15
Allgemein: x = c + m*k, für alle k (1..unendlich) aus den natürliche Zahlen N
In diesem Fall: x = 8 +4*15k {k = 0 ... } (für ganze Zahlen: 8 4*15k {k = 0 ... } )
Hapi