Technische Universität Clausthal WS 1999/2000 Institut für Mathematik 06.12.1999 Prof. Dr. L. G. Lucht 7. Übungsblatt

Elementare Zahlentheorie

Diese Aufgaben werden in der Übungsstunde vom 15.12.1999 besprochen;

Abgabe schriftlicher Lösungen (Aufgaben 1 bis 4) bitte am Montag, 13.12.1999, vor der Vorlesung.

1. Zeigen Sie, daß sich keine Zahl der Form 4^{m} (8k + 7) mit m, k ∈ ℕ_{0} als Summe von drei Quadratzahlen darstellen läßt.

2. Es sei p eine ungerade Primzahl. Zeigen Sie ∑_{n=1}^{p−2} (\frac{n(n + 1)}{p}) = −1 .

Hinweis : n(n + 1) = n^{2} (1 + n^{−1}) .

3. Es seien a, b, α, β, d ∈ ℝ und d > 0. Zeigen Sie durch Rechnung im Komplexen

(a^{2} + d b^{2})(α^{2} + d β^{2}) = (aα ± d bβ)^{2} + d (aβ ∓ bα)^{2}.

4. Zeigen Sie, daß jede Primzahl p ≡ 1 mod 6 eine Darstellung p = x^{2} + 3 y^{2} mit x, y ∈ ℤ besitzt und daß keine andere Primzahl p ≠ 3 diese Eigenschaft aufweist.

5. Arbeiten Sie den Beweis des folgenden Satzes so durch, daß Sie ihn vortragen können. Zur Erinnerung : Eine zusammengesetzte Zahl n ∈ ℕ heißt Carmichael-Zahl, wenn x^{n} ≡ x mod n für alle x ∈ ℕ mit ggT (n, x) = 1 gilt.

Satz.

(a) Jede Carmichael-Zahl ist ungerade.

(b) Keine Carmichael-Zahl ist durch eine Quadratzahl > 1 teilbar.

(c) Ist n Carmichael-Zahl, so gilt (p − 1) | (n − 1) für jeden Primteiler p von n.

(d) Jede Carmichael-Zahl besitzt mindestens drei Primfaktoren.

(e) Genau dann ist n Carmichael-Zahl, wenn n = p_{1} ⋯ p_{r} mit r ≥ 3 verschiedenen ungeraden Primzahlen p_{ϱ} gilt, die (p_{ϱ} − 1) | (n − 1) erfüllen.

Beweis des Satzes.

(a) Angenommen, es ist n = 2m mit ganzem m ∈ ℕ eine Carmichael-Zahl. Dann gilt für jedes x ∈ ℤ mit ggT (x, n) = 1 stets x^{2m} − x ≡ 0 mod n, speziell für x = −1 also 2 ≡ 0 mod n und damit n = 2 entgegen der Definition (als Carmichael-Zahl ist n nicht prim).

(b) Vorbemerkung : Wir verwenden (ohne Beweis) die Existenz von Primitivwurzeln modulo ungerader Primzahlpotenzen p^{k} (Aufgabe 5 (b) von Übungsblatt 6 behandelte nur den Fall k = 1).

Angenommen, es ist n nicht quadratfrei. Dann existieren p ∈ ℙ mit n = p^{k}m, k ≥ 2, p ∤ m, und nach der Vorbemerkung eine Primitivwurzel g mod p^{k}. Nach dem Chinesischen Restsatz ist das lineare Kongruenzsystem

a ≡ g mod p^{k}
a ≡ 1 mod m

(wegen p ∤ m) lösbar mit einer eindeutigen Lösung a mod p^{k}m = n. Es ist a zu n teilerfremd : Wir nehmen die Existenz einer Primzahl q mit q | a und q | p^{k}m an. Wäre q = p, so würde p die Primitivwurzel g mod p^{k} teilen, was unmöglich ist. Also gilt q | m (und q | a) im Widerspruch zu a ≡ 1 mod m. Aus ggT (a, n) = 1 folgt a^{n−1} ≡ 1 mod n (da n Carmichael-Zahl ist). Hieraus folgt wegen a^{n−1} ≡ g^{n−1} mod p^{k}

g^{n−1} ≡ 1 mod p^{k}.

Nun hat aber g die Ordnung φ(p^{k}) = p^{k−1}(p − 1), und daher gilt

p^{k−1}(p − 1) | n − 1. (∗)

Aus k ≥ 2 folgt p | n − 1 im Widerspruch zu p | n. Also ist n quadratfrei.

(c) Es sei p ein Primteiler von n. Nach (a) können wir n = pm mit p ∤ m annehmen. Aus der Teilerbeziehung (??) mit k = 1 kommt p − 1 | n − 1.

(d) Wir nehmen an, die Carmichael-Zahl n = pq sei aus den Primzahlen p, q zusammengesetzt. Nach (c) gilt p − 1 | pq − 1, und aus pq − 1 = (p − 1)q + q − 1 folgt p − 1 | q − 1. Analog sieht man q − 1 | p − 1. Dann ist aber p = q im Widerspruch zu (b).

(e) Zu zeigen ist nur noch, daß n | (x^{n} − x) für alle x ∈ ℤ mit ggT (x, n) = 1 gilt, wenn n aus wenigstens drei verschiedenen ungeraden Primzahlen p mit (p − 1) | (n − 1) zusammengesetzt ist. In der Tat ist für jeden Primteiler p von n mit λ := \frac{n−1}{p−1} ∈ ℕ wegen der kleinen Fermatschen Satzes die Kongruenz

x^{n} = x^{n−1} x = (x^{p−1})^{λ} x ≡ x mod p

oder gleichwertig p | (x^{n} − x) für alle x ∈ ℤ erfüllt, woraus n | (x^{n} − x) für (sogar) alle x ∈ ℤ kommt. Folglich ist n Carmichael-Zahl.