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

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

• $x^{2}\equiv 2\;({\text{mod}}\ 5)$
• $x^{2}\equiv 2\;({\text{mod}}\ 7)$

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches

Restklassen

Restklassen

Restklassen modulo $m$:

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

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 $\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}\equiv 2\;({\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 2? Keines, daher keine Lösung.

b) $x^{2}\equiv 2\;({\text{mod}}\ 7)$

Modulo 7 bedeutet, daß die Restklassen 0,1,2,3, 4, 5 und 6 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 = 2, 4 * 4 = 16 = 2, 5 * 5 = 25 = 4, 6 * 6 = 36 = 1

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

In diesem Fall: x1 = 3 + 7k {k = 0 ... $\infty$}, x2 = 4 + 7k {k = 0 ... $\infty$ (Für ganze Zahlen 3 $\pm$ 7k bzw. 4 $\pm$ 7k)

Hapi