Blatt 4

Sommersemester 2016
Tobias Roßmann
Elementare Zahlentheorie
Blatt 4
?
Abgabe bis 12 Uhr am 9. Mai 2016 im Postfach Ihres Tutors.
Aufgabe 1 (1+1+2 Punkte). Sei n ∈ N. Zeigen Sie:
(i) ϕ(n) ist gerade für n > 3.
(ii) ϕ(2n) = ϕ(n) gilt genau dann, wenn n ungerade ist.
(iii) Es gibt nur endlich viele x ∈ N mit ϕ(x) = n.
Aufgabe 2 (2+2 Punkte).
(i) Seien a, n ∈ N und sei p ein Primteiler von an − 1 mit p 6≡ 1 (mod n). Zeigen Sie,
dass es einen Teiler d ∈ N von n mit d 6= n und p | (ad − 1) gibt.
(ii) Seien p und ` verschiedene ungerade Primzahlen. Sei a ∈ Z mit ggT(a, p`) = 1.
Zeigen Sie, dass aϕ(p`)/2 ≡ 1 (mod p`).
Definition. Seien a ∈ Z und n ∈ N.
(i) Wir nennen a nilpotent modulo n, falls es ein k ∈ N mit ak ≡ 0 (mod n) gibt.
(ii) Wir nennen a invertierbar modulo n, falls es ein b ∈ Z mit ab ≡ 1 (mod n) gibt.
Aufgabe 3 (1+1+1+1 Punkte). Seien a ∈ Z und n ∈ N. Wir setzen
Y
r(n) :=
pmin(νp (n),1) .
p prim
Zeigen Sie:
(i) a ist genau dann nilpotent modulo n, wenn a ≡ 0 (mod r(n)).
(ii) a ist genau dann invertierbar modulo n, wenn a invertierbar modulo r(n) ist.
(iii) Ist n eine Primzahlpotenz, so ist a stets nilpotent oder invertierbar modulo n.
(iv) Ist n zusammengesetzt, so gibt es eine ganze Zahl, welche weder nilpotent noch
invertierbar modulo n ist.
Aufgabe 4 (4 Punkte). Seien p eine ungerade Primzahl, a ∈ Z und R ein vollständiges
Restsystem modulo p. Es bezeichne N die Anzahl jener Paare (x, y) ∈ R×R mit x2 −y 2 ≡ a
(mod p). Zeigen Sie, dass
(
p − 1,
falls a 6≡ 0 (mod p),
N=
2p − 1, falls a ≡ 0 (mod p).

Download Report