Universität Karlsruhe (TH) Karlsruhe, 8.6.1990 Mathematisches Institut II Prof. Dr. H.-W. Leopoldt

Elementare Zahlentheorie — Übungsblatt 7

Aufgabe 30 (4 Punkte) Bestimmen Sie für die folgenden Werte von m alle Lösungen der Kongruenz x^{4} − 8x + 12 ≡ 0 (mod m):

(a) m = 128,

(b) m = 81,

(c) m = 125,

(d) m = 49.

Aufgabe 31 (4 Punkte) Sei A die abelsche Gruppe

(a) A = (ZZ/ZZp^{n} )^{×} (p ∈ IP, n ∈ IN) bzw. allgemeiner

(b) A = (ZZ/ZZm)^{×} (m ∈ IN).

Bestimmen Sie die Anzahl der Quadrate (Elemente der Form a = b^{2} mit b ∈ A) in A. (Hinweis: Benutzen Sie die Darstellung als direktes Produkt zyklischer Gruppen.)

Aufgabe 32 (7=3+2+2 Punkte) Eine natürliche Zahl n heißt Carmichaelzahl oder Pseudo-Primzahl, falls n > 1 und für jedes a ∈ ZZ mit (a, n) = 1 die Kongruenz a^{n−1} ≡ 1 (mod n) gilt und n dennoch keine Primzahl ist. Zeigen Sie:

(a) n ist genau dann eine Carmichaelzahl, wenn n die Primfaktorzerlegung n = p_{1} · p_{2} · . . . · p_{t} mit t ≥ 2 und paarweise verschiedenen p_{i} besitzt, für die p_{i} − 1 | n − 1 (i = 1, …, t) gilt.

(b) Jede Carmichaelzahl ist ungerade und hat mindestens 3 Primfaktoren.

(c) Die kleinste Carmichaelzahl ist 561.

Aufgabe 33 (5 Punkte) Für m ∈ IN und a, b ∈ ZZ sei

(\frac{a, b}{m}) = ∑_{x∈( ZZ / ZZm)^{×}} e2πi · \frac{ax+bx^{−1}}{m}

wobei x^{−1} die Inverse von x in (ZZ/ZZm)^{×} sei. Zeigen Sie:

(a) (\frac{a, b}{m}) hängt nur von den Restklassen a mod m und b mod m ab.

(b) (\frac{a, b}{m}) ∈ IR.

(c) (\frac{a, b}{m}) = (\frac{b, a}{m}).

(d) Für h ∈ (ZZ/ZZm)^{×} gilt (\frac{ah, b}{m}) = (\frac{a, bh}{m}).

(e) Sei m = m_{1} · . . . · m_{r} mit paarweise teilerfremden m_{i} ∈ IN. Wie üblich sei m̃_{i} = \frac{m}{m_{i}} . Zeigen Sie:

(\frac{a_{1}, 1}{m_{1}}) · . . . · (\frac{a_{r}, 1}{m_{r}}) = (\frac{m̃_{1}^{2}a_{1} + … + m̃_{r}^{2}a_{r}, 1}{m})

Aufgabe 34 (7 Punkte) Bestimmen Sie alle Lösungen der Gleichung 2x^{2} + 2x + 1 = 5^{n} mit x ∈ ZZ und n ∈ IN_{0} . Anleitung: Sei (x, n) eine Lösung. Zeigen Sie:

(a) In Γ = ZZ[i] gilt x ± (x + 1)i = u · (1 + 2i)^{n} mit einer Einheit u ∈ Γ^{×}.

(b) Definiert man a_{n}, b_{n} ∈ ZZ durch a_{n} + 2b_{n} · i = (1 + 2i)^{n}, so gelten für n = 2^{t} · s mit ungeradem s ∈ IN und t ≥ 2 die Kongruenzen

\begin{aligned}a_{n} & ≡ 1 − 2^{t+1} · s (mod 2^{t+4}) , \\ 2b_{n} & ≡ 2^{t+1} · 5 · s (mod 2^{t+4}) . \end{aligned}

(c) Es ist n ∈ {0, 1, 2}.

Abgabe: Bis spätestens Freitag, 15.6.1990, 11.15 Uhr in den Kasten bei Zi. 308 des Mathematikgebäudes oder in der Vorlesung im Hörsaal Hauptbau.