TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 64

Aus VoWi
Zur Navigation springen Zur Suche springen

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

  • 3x\equiv9\;(\text{mod}\ 11)
  • 3x\equiv9\;(\text{mod}\ 12)

Hilfreiches[Bearbeiten]

Restklassen[Bearbeiten]

Restklassen modulo m:

\overline{a}=\lbrace a+km|k\in\mathbb{Z}\rbrace_{m}

Lösung von Hapi[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]

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

Mein Lösungsweg:

\Z_{11}=\{\overline 0,\overline 1,\overline 2,\overline 3,\overline 4,\overline 5,\overline 6,\overline 7,\overline 8,\overline 9,\overline {10}\}

\overline 9=\{9+11\Z\}=9,20,31,42,53,64,75,86,97,...

Man betrachtet die Elemente von \overline 9 die durch 5 teilbar sind (wegen 5x).

5\nmid 9, 5\mid 20, 5\nmid 31, 5\nmid 42, 5\nmid 53, 5\nmid 64, 5\mid 75, ...

d.h. x=\{\frac{20}{5}, \frac{75}{5}, ...\}=\{4, 15, ...\}=4+k11

Links[Bearbeiten]

Ähnliche Beispiele: