Transcript
Prof. Dr. Felix Leinen
11. Mai 2016
¨ Ubungen zur LAG + im Sommer 2016 – Blatt 4
Abgabe der Aufgaben bis Mittwoch, 18. Mai 2016 um 10:00 Uhr. Bei allen Aufgaben ist der Rechenweg ausf¨ uhrlich darzustellen!
1. (a)
I
Stellen Sie die Multiplikationstafel von Z/15 Z auf.
I
Welche Elemente in Z/15 Z sind Nullteiler ? Wir nennen x 6= 0 einen Nullteiler, falls xy = 0 ist f¨ ur ein y 6= 0.
I
Welche Elemente in Z/15 Z sind invertierbar ?
I
Finden Sie zu jedem invertierbaren Element in Z/15 Z das Inverse.
[4 P]
(b) Nun sei 1 ≤ n ∈ N und 0 6= x ∈ Z/n Z. Zeigen Sie: Genau dann ist x ein Nullteiler in Z/n Z, wenn x in Z/n Z nicht invertierbar ist.
[3 P]
2. (a) L¨osen Sie das folgende diskrete Logarithmusproblem: Bestimmen Sie eine nat¨ urliche Zahl k mit 13k ≡ 29 .
[2 P]
41
(b) Berechnen Sie die Inverse zu [3231323] in Z/368131767 Z.
[3.5 P]
3. (a) Zeigen Sie: F¨ ur a, b ∈ N \ {0} und Primzahlen p 6= q gilt stets ϕ(pa q b ) = (pa − pa−1 ) (q b − q b−1 ) . Verwenden Sie unter anderem Aufgabe 1(b).
[3 P]
(b) Bestimmen Sie die Anzahl der invertierbaren Elemente in Z/16637 Z.
[2 P]
(c) Berechnen Sie 349149 mod 16637 .
[1.5 P]
4. Es seien m und n zwei fest gew¨ ahlte teilerfremde nat¨ urliche Zahlen ≥ 1 . (a) Zeigen Sie, daß eine Abbildung Θ : Z/mnZ −→ Z/mZ × Z/nZ gegeben ist durch Θ([d]mn ) = [d]m , [d]n f¨ ur alle d ∈ Z. ¨ Hierbei bezeichne [d]s die Aquivalenzklasse von d in Z/sZ.
[1.5 P]
(b) Kl¨ aren Sie, ob die Abbildung Θ im Fall m = 4 und n = 6 surjektiv ist.
[1.5 P]
Im folgenden seien m und n stets teilerfremd, also 1 = a m + b n f¨ ur gewisse a, b ∈ Z. (c) Zeigen Sie:
Ist d = d1 b n + d2 a m, so gilt d ≡ d1 und d ≡ d2 . m
n
[1 P]
(d) Folgern Sie, daß Θ jetzt surjektiv ist.
[1 P]
(e) Folgern Sie, daß Θ dann auch injektiv ist.
[2 P]
(f) Zeigen Sie: Genau dann ist [d]mn invertierbar in Z/mnZ, wenn [d]m invertierbar in Z/mZ und [d]n invertierbar in Z/nZ ist.
[4 P]
