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

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

• $8x\equiv 4\;({\text{mod}}\ 16)$
• $8x\equiv 4\;({\text{mod}}\ 15)$

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}$

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-a) gilt und somit m den Term (b-a) 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 b 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 15

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 ... $\infty$} (für ganze Zahlen: 8 $\pm$ 4*15k {k = 0 ... $\infty$} )

Hapi

Lösung zu 57b lt Übung vom 05.11.2007

ggt (8,15)= 1 1|4 Es gibt genau eine Lösung. L = {8}

Die kontrekte Lösung kann durch Probieren herausgefunden werden (durch Einsetzen der Zahlen von 0-14 für x, bzw. 7 bis -7 wenn man keine so grossen Zahlen will).

PS.: Lt. Prof ist die Formel in Lösung 57 b von Hapi falsch!

2 Lösungen lt. Prof. Panholzer

Eine Möglichkeit, ist einfach eine Tabelle mit allen Restklassen zu erstellen und dann eine Spalte mit '8x' mod 15 bzw 16 anzulegen und dann zu schauen ob dort die Lösung, also 4, vorkommt. Für mod 16:

${\bar {x}}$ mod 16	${\bar {8x}}$ mod 16
0	0
1	8
2	0
3	8
4	0
5	8
6	0
7	8
8	0
9	8
10	0
11	8
12	0
13	8
14	0
15	8
16	0

Wie man sehen kann kommt die gesuchte Lösung 4 niemals vor.

Für mod 15:

${\bar {x}}$ mod 15	${\bar {8x}}$ mod 15
0	0
1	8
2	1
3	9
4	2
5	10
6	3
7	11
8	4
9	12
10	5
11	13
12	6
13	14
14	7
15	0

Die gesuchte Lösung 4 kommt hier vor und zwar in der Restklasse 8, also ist die Lösung x=8.

Der zweite Lösungsansatz geht über den Euklidischen Algorithmus und die Zerlegung in Linearfaktoren. Ich demonstrier hier mal nur für mod 15 weil dann auch ein Ergebnis rauskommt. Wir suchen den ggT von 8 und 15 und rechnen:

15 = 8*1 + 7
8 = 7*1 + 1
7 = 1*7 + 0

Der ggT(15,8) ist also 1. Jetzt können wir diesen ggT als Linearkombination ganzer Zahlen darstellen (vgl. Buch, Satz 1.18).

1 = 8 - 7*1
1 = 8 - (15 - 8*1)*1
1 = 8 - 15*1 + 8*1
1 = 8*2 - 15*1

Jetzt multiplizieren wir mit der gesuchten Lösung 4 auf beiden Seiten.

4 = 8*(2*4) - 15*4

Erinnert doch verdächtig an unsere Gleichung $8x\equiv 4\;({\text{mod}}\ 15)$. Das Ergebnis ist also 2*4 = 8.

--Lösung von Fabb 12:25, 7. Nov 2007 (CET)

Ich denke das mit der Tabelle stimmt nicht ganz, denn wir stellen auf der linken Seite nicht die Restklassen von 15 bzw 16 dar, sondern nur die Zahlen, die wir in die Formel $8x$ einsetzen. Das was auf der rechten Seite rauskommt ist meiner Meinung nach die Restklasse mod 15 bzw 16. Wir würden uns ja sonst widersprechen, denn 4 liegt ja natürlich bezüglich 15 bzw 16 in der Restklasse ${\bar {4}}$ und nicht in der Restklasse ${\bar {8}}$

Die Lösung ist dann mMn $x=8+15k,k\in Z$

MarS

Oder einfach so

a.)
8x $\equiv$ 4 mod 16
8x=16*k+4
2x=4*k+1
x=(4*k+1)/2
für k=1:
x=2,5 Keine Lösung in Z!

b.)
8x $\equiv$ 4 mod 15
2x $\equiv$ 1 mod 15
2x=15*k+1
x=(15*k+1)/2
für k=1:
x=8

edit[ab 2te Zeile bei b.)]: 2x $\equiv$ 16 mod 15
dann einfach durch 2 dividieren x = 8 weil 1 mod 15, gleich 16 mod 15 (beide rest 1)