Difference between revisions of "TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 62"

From VoWi
Jump to navigation Jump to search
m
 
Line 7: Line 7:
  
  
==Hilfreiches==
+
==[[Vorlagen|Hilfreiches]]==
 
{{Restklassen}}
 
{{Restklassen}}
  

Revision as of 15:46, 3 November 2007

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

  • <amsmath>8x\equiv4\;(\text{mod}\:16)</amsmath>
  • <amsmath>8x\equiv4\;(\text{mod}\:15)</amsmath>


Hilfreiches

Vorlage:Restklassen

Siehe Beispiele 57-60

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.


ad a) 8x \equiv 4 mod 16, 2x \equiv 1 mod 4

Es gibt keine Lösung, da b < als a ist, b kann aber kein Bruch sein!

Oder etwas mehr mathematisch: der ggt von 8x und 16 ist 8, 8 teilt nicht 4, daher keine Lösung!


ad b) 8x \equiv 4 mod 15, 2x \equiv 1 mod 15

D.h. es gibt eine Lösung denn b teilt ax, hat aber keinen ggt mit c (15)

Denn 8*8 = 64 \equiv 4 mod 16

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

In diesem Fall: x = 8 +4*15k {k = 0 ... \infin} (für ganze Zahlen: 8 \pm 4*15k {k = 0 ... \infin} )


Hapi

Lösungsvorschlag von Schnuffel:

57a) lt. Mathematik für Informatik: Zwei Zahlen a,b Elemente von Z heißen kongruent modulo m, falls m ein Teiler von b-a ist.

dh 16 teilt 8x - 4

Die Lösung wurde eine rationale Zahl ergeben, das Beispiel ist daher nicht in Z lösbar.