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

Lösen Sie die folgenden Kongruënzen (d.h. Gleichungen in Restklassen) bzw. beweisen Sie die Unlösbarkeit:
a) $3x\equiv 9\;({\text{mod}}\ 11)$
b) $3x\equiv 9\;({\text{mod}}\ 12)$

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[Bearbeiten | Quelltext bearbeiten]

Restklassen

Restklassen[Bearbeiten | Quelltext bearbeiten]

Restklassen modulo $m$ :

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

Lösung von Kernkraftwerk[Bearbeiten | Quelltext bearbeiten]

Allgemeines zur Lösungsstrategie: Hier eine kleine Wie- derholung. Es ist übrigens durchaus erlaubt, beim Test alle Werte durchzuprobieren um so auf eine Lösung von ax $\equiv$ b mod m zu kommen. Für alle, die es genauer wissen wollen hier ein kleiner Text mit Beispielen am Ende. Wir haben eine Kongruenz der Form ax $\equiv$ b mod m. Beispiele daf¨ur w¨aren z.B. die Kongruenzen aus der Übung: 8x $\equiv$ 4 mod 16 oder 8x $\equiv$ 4 mod 15. Ein sehr hilfreicher Satz ist der folgende: ax $\equiv$ b mod m ist lösbar genau dann wenn ggT (a, m) teilt b. Wie gehe ich das Problem jetzt an?

1. Schritt: Überprüfe ob ggT (a, m) die Zahl b teilt: Wenn nein sind wir hier fertig und können sagen: Es gibt keine Lösung! Wenn ja: weiter zum naechsten Schrit

2. Schritt: Schritt: Dividieren durch den ggT (a, m)

Ich nenne den ggT (a, m) jetzt d. Ich kann nun die ganze Gleichung durch d dividieren. Dann erhalte ich aus a′ = a d , b′ = b d und m′ = m d eine neue Kongruenz der Form: a′x ≡ b′ mod m′ Hier gilt ggT (a′, m′) = 1, das heißt es gibt ein Inverses modulo m′, also ein c mit a′c ≡ 1 mod m′ oder anders ausgedrückt: Es gibt c und e mit 1 = a′c + m′e. Diese beiden Werte berechne ich mir mit dem Euklidischen Algorithmus.

3. Schritt: Multiplizieren mit c

Ich kann nun die ganze Kongruenz mit c multiplizieren. Daraus ergibt sich: ca′x ≡ cb′ mod m′ also (weil ca′ ≡ 1 mod m) x ≡ cb′ mod m′ Die Lösung ist also {..., cb′ − 2m, cb′ − m, cb′, cb′ + m, cb′ + 2m, ...} oder anders gesagt cb′ + jm, j ∈ Z

Bsp 1: 3x $\equiv$ 9 mod 11 1.Schritt: ggT(3,11) = 1 (teilerfremd, nona),1 teilt 9, das heißt es gibt eine Lösung.

2. Schritt: Dividiere die Kongruenz durch 1, es ergibt sich die "neue" Kongruenz: 3x $\equiv$ 9 mod 11 Wir lösen den ggT in Linearfaktoren auf: ggT(3,11) = 1 = 3 * 4 - 11 * 1 Das inverse c: 4 mod 11 = 4; x $\equiv$ 4*9 mod 11

Oder bessergesagt Die Lösung ist 36+j*11, j ∈ Z

Bsp 2: 3x ≡ 9 mod 12 1. Schritt: ggT (3, 12) = 3, 3 teilt 9, das heißt es gibt eine Lösung. 2. Schritt: Dividiere die Kongruenz durch 3, es ergibt sich die neue Kongruenz x ≡ 3 mod 4 Die Lösungen sind direkt ablesbar, sie sind {. . . , −5, −1, 3, 7, 11, . . . } oder schöner 3+j∗4, j ∈ Z.

Kernkraftwerk ---

Lösung von Hapi[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 $\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.

ad a) 3x $\equiv$ 9 mod 11, x $\equiv$ 3 mod 11 d.h. 11 | (3-x),

Es gibt einen größten gemeinsamen Teiler für die Werte a und b, daher lösbar.

Allgemein: x = c + m*k, für alle k (1..unendlich) aus den natürliche Zahlen N

In diesem Fall: x = 3 + 11*k für alle k (1.. $\infty$ ) = 14,25,36,...

ad b) 3x $\equiv$ 9 mod 12, x $\equiv$ 3 mod 4 d.h. 4 | (3-x), oder 12 | (9 - 3x)

D.h. es gibt eine Lösung, weil der ggT von (3x,12) die Zahl 9 teilt.

Allgemein: x = c + m*k, für alle k (1..unendlich) aus den natürliche Zahlen N

In diesem Fall: x = 3 + 4*k für alle k (1.. $\infty$ ) = 7,11,15,...

Hapi

Anmerkung: Die erste Version einer Lösung für 76a war falsch! Habe die Gesetzmäßigkeiten falsch beurteilt.

Beispiel:

8x $\equiv$ 4 mod 16, div 4 = 2x $\equiv$ 1 mod 4, unlösbar, da b < a

8x $\equiv$ 4 mod 15, div 4 = 2x $\equiv$ 1 mod 15, lösbar, x = 8 +1*15k

5x $\equiv$ 9 mod 11, unlösbar, da kein gemeinsamer Teiler

Anmerkung von sunmmoonlight[Bearbeiten | Quelltext bearbeiten]

${\text{5x}}\equiv {\text{9 mod 11}}$ , ist lösbar ${\text{x}}={\text{4 + 11*k}}$

Mein Lösungsweg:

$\mathbb {Z} _{11}=\{{\overline {0}},{\overline {1}},{\overline {2}},{\overline {3}},{\overline {4}},{\overline {5}},{\overline {6}},{\overline {7}},{\overline {8}},{\overline {9}},{\overline {10}}\}$