¨Ubungen zur LAG+ im Sommer 2016 – Blatt 4

Prof. Dr. Felix Leinen
11. Mai 2016
Übungen 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 ausführlich 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 für 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) Lösen Sie das folgende diskrete Logarithmusproblem:
Bestimmen Sie eine natürliche 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:
Für 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 gewählte teilerfremde natürliche Zahlen ≥ 1 .
(a) Zeigen Sie, daß eine Abbildung Θ : Z/mnZ −→ Z/mZ × Z/nZ gegeben ist durch
Θ([d]mn ) = [d]m , [d]n
für alle
d ∈ Z.
Hierbei bezeichne [d]s die Äquivalenzklasse von d in Z/sZ.
[1.5 P]
(b) Klären 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 für 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]

Download Report