Diskrete Mathematik für Informatiker/ Übung mit der Lösung PDF

Preview

Summary

Download Diskrete Mathematik für Informatiker/ Übung mit der Lösung PDF

Description

Grundlagen der diskreten Mathematik Blatt Nr. 4

Lösungen der ÜBUNGSAUFGABEN Hechler/Kallrath

zu Übungsaufgabe 4.1 a) Erstellen Sie die Additions- und die Multiplikationstabelle in Z7 . b) Bestimmen Sie für jedes Element in Z7 die additive Inverse. Welche Elemente haben eine multiplikative Inverse in Z7 ? c) Welche Elemente haben eine multiplikative Inverse in Z8 , Z10 , Z15 , Z43 ? Lösungsvorschlag: zu a) + 0 1 2 3 4 5 6

0 0 1 2 3 4 5 6

1 1 2 3 4 5 6 0

2 2 3 4 5 6 0 1

3 3 4 5 6 0 1 2

4 4 5 6 0 1 2 3

5 5 6 0 1 2 3 4

6 6 0 1 2 3 4 5

· 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0

1 0 1 2 3 4 5 6

2 0 2 4 6 1 3 5

3 0 3 6 2 5 1 4

4 0 4 1 5 2 6 3

5 0 5 3 1 6 4 2

6 0 6 5 4 3 2 1

zu b): Additive Inverse zu jedem Element i ist 7 − i, i = 0, 6 Multiplikative Inverse (außer 0): zu 1 ist 1, zu 2 ist 4, zu 3 ist 5, zu 4 ist 2, zu 5 ist 3, zu 6 ist 6. zu c): Element a hat ein inverses Element in Zn , wenn ggT (a, n) = 1. In Z8 haben {1, 3, 5, 7} ein inverses Element. In Z10 haben {1, 3, 7, 9} ein inverses Element. In Z15 haben {1, 2, 4, 7, 8, 11, 13, 14} ein inverses Element. In Z43 haben {1, ..., 42} ein inverses Element. zu Übungsaufgabe 4.2 Berechnen Sie den Wert der Eulerschen ϕ-Funktion, ϕ(n), für n = 8, 9, 10, 15, 43, 837.

Lösungsvorschlag: ϕ(8) = ϕ(23 ) = 23 − 22 = 8 − 4 = 4 ϕ(9) = ϕ(32 ) = 32 − 31 = 9 − 3 = 6 ϕ(10) = ϕ(2 · 5) = ϕ(2) · ϕ(5) = 1 · 4 = 4 ϕ(15) = ϕ(3 · 5) = ϕ(3) · ϕ(5) = 2 · 4 = 8 ϕ(43) = 42 (für Primzahlen ϕ(p) = p − 1) ϕ(837) = ϕ(33 · 31) = ϕ(33 ) · ϕ(31) = (33 − 32 ) · 30 = 18 · 30 = 540 Vergeliche Werte ϕ(8), ϕ(10), ϕ(15) mit Aufgabe 1(c). zu Übungsaufgabe 4.3 Bestimmen Sie die multiplikative Inverse zu 5 in Z8 , zu 7 in Z9 , zu 5 in Z10 , zu 7 in Z10 , zu 11 in Z15 , zu 2 in Z99 . Lösungsvorschlag: zu 5 in Z8 : 5, da 5 · 5 ≡ 25 ≡ 1 mod 8 zu 7 in Z9 : 4, da 7 · 4 ≡ 28 ≡ 1 mod 9 zu 5 in Z10 : keine Inverse, da ggT (5, 10) 6= 1 zu 7 in Z10 : 3, da 7 · 3 ≡ 21 ≡ 1 mod 10 zu 11 in Z15 : 11, da 11 · 11 ≡ 121 ≡ 1 mod 15 Hinweis: Man löse eine diophantische Gleichung: 11x − 1 = 15k ; Allgemeine Lösung: x = 15c − 4; k = 11c − 3. Kleinste positive Lösung für x bekommt man für c = 1, also x = 11. zu 2 in Z99 : 50, da 2 · 50 ≡ 100 ≡ 1 mod 99 Hinweis: Man löse eine diophantische Gleichung: 2x − 1 = 99k ; Allgemeine Lösung: x = 99a − 49; k = 2a − 1. Kleinste positive Lösung für x bekommt man für a = 1, also x = 50.

zu Übungsaufgabe 4.4 Sei a, b, c, d ∈ Z, m ∈ N und a ≡ b mod m, c ≡ d mod m. Beweisen Sie, dass ac ≡ bd mod m. Lösungsvorschlag: Es gilt: a ≡ b mod m [1] c ≡ d mod m [2] Zeige, dass ac ≡ bd mod m. Wenn [1] gilt, dann ac ≡ bc mod m [3] Wenn [2] gilt, dann cb ≡ db mod m [4] Aus [3] folgt: (ac − bc) = mk1 (lt. Definition) Aus [4] folgt: (bc − bd ) = mk2 (lt. Definition) [3] + [4]: (ac − bc) + (bc − bd) = m(k1 + k2 ) ⇒ ac − bd = m(k1 + k2 ) ⇔ ac ≡ bd mod m. zu Übungsaufgabe 4.5 Lösen Sie die folgenden lineare Gleichungen in Zn . Geben Sie eine allgemeine Formel für die Lösung an. a) x + 3 = 2 in Z4 b) 3 + 10x = 12 in Z13 c) 10x + 4 = 9 in Z25

Lösungsvorschlag: zu a): x + 3 = 2 in Z4 ⇔ x + 3 ≡ 2 mod 4 Additive Inverse zu 3 in Z4 ist 1. x + 3 + 1 ≡ 2 + 1 mod 4 x ≡ 3 mod 4 x = 4k + 3 für k ∈ Z zu b): 3 + 10x = 12 in Z13 ⇔ 3 + 10x ≡ 12 mod 13 Additive Inverse zu 3 ist Z13 ist 10. 10x ≡ 12 + 10 ≡ 22 ≡ 9 mod 13 ggT (10, 13) = 1 ⇒ lösbar Inverse zu 10 in Z13 ist 4: 4 · 10 = 39 + 1 ≡ 1 mod 13 10 · 4 · x ≡ 9 · 4 mod 13 x ≡ 36 mod 13 x ≡ 10 mod 13 x = 13k + 10 für k ∈ Z zu c): 10x + 4 = 9 in Z25 Additive Inverse zu 4 ist Z25 ist 21. 10x ≡ 9 + 21 ≡ 30 ≡ 5 mod 25 ggT (10, 25) = 5, 5 ist Teiler von 5 ⇒ 5 Lösungen in Z25 . Es wird durch ggT (10, 25) = 5 geteilt und die Gleichung 2x ≡ 1 mod 5 gelöst. Multiplikative Inverse zu 2 in Z5 ist 3, 3 · 2 · x ≡ 3 · 1 mod 5 x ≡ 3 mod 5 Betrachte alle positiven Repräsentanten in Restklasse [3] in Z5 , die kleiner als 25 sind: [3] = {... − 7, −2, 3, 8, 13, 18, 23, 28, ...} Lösungen in Z25 : x1 = 25k + 3, x2 = 25k + 8, x3 = 25k + 13, x4 = 25k + 18 x5 = 25k + 23 für k ∈ Z...