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

Aus VoWi
< TU Wien:Mathematik 1 UE (diverse)‎ | Übungen WS06
Version vom 22. Februar 2009, 19:06 Uhr von Migration-bot (Diskussion | Beiträge) (hat „Beispiel 77“ nach „TU Wien:Mathematik 1 UE (diverse)/Übungen WS06/Beispiel 77“ verschoben: import move)
(Unterschied) ← Nächstältere Version | Aktuelle Version (Unterschied) | Nächstjüngere Version → (Unterschied)
Zur Navigation springen Zur Suche springen

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

  • x^2\equiv1\;(\text{mod}\ 3)
  • x^2\equiv1\;(\text{mod}\ 5)


Hilfreiches[Bearbeiten]

Vorlage:Restklassen


Lösungsversuch[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 \equiv 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 \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 c teilt.


a) x^2\equiv1\;(\text{mod}\ 3)

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 ... \infin}, x2 = 2 + 3k {k = 0 ... \infin} (Für ganze Zahlen 1 \pm 3k bzw. 2 \pm 3k)


b) x^2\equiv1\;(\text{mod}\ 5)

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 ... \infin}, x2 = 4 + 5k {k = 0 ... \infin (Für ganze Zahlen 1 \pm 5k bzw. 4 \pm 5k)


Hapi