TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 77

From VoWi
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

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


Hilfreiches

Vorlage:Restklassen


Lösungsversuch

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.


a)

Modulo 3 bedeutet, daß die Restklassen 0,1 und 2 vorliegen. Jetzt kann man einfach die Produkte dieser Restklassen in einer Tabelle ausrechenen oder nur die Produkte:

   0 * 0 = 0, 1 * 1 = 1, 2 * 2 = 4 = 1 

Somit hat man die Lösung, denn die Produkte welcher Restklassen ergeben die Restklasse 1? Restklasse 1 und 2.

In diesem Fall: x1 = 1 + 3k {k = 0 ... }, x2 = 2 + 3k {k = 0 ... } (Für ganze Zahlen 1 3k bzw. 2 3k)


b)

Modulo 5 bedeutet, daß die Restklassen 0,1,2,3 und 4 vorliegen. Jetzt kann man einfach die Produkte dieser Restklassen in einer Tabelle ausrechenen oder nur die Produkte:

  0 * 0 = 0, 1 * 1 = 1, 2 * 2 = 4, 3 * 3 = 9 = 4, 4 * 4 = 16 = 1  

Somit hat man die Lösung, denn die Produkte welcher Restklassen ergeben die Restklasse 1? Restklasse 1 und 4.

In diesem Fall: x1 = 1 + 5k {k = 0 ... }, x2 = 4 + 5k {k = 0 ... (Für ganze Zahlen 1 5k bzw. 4 5k)


Hapi