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

Elementare Zahlentheorie — Übungsblatt 2

Aufgabe 3 (7 Punkte) Zeigen Sie:

(a) M_{n} = 2^{n} − 1 (n ∈ IN) ist nur dann Primzahl, wenn n Primzahl ist. M_{n} heißt Mersennesche Primzahl.

(b) 2^{n} + 1 (n ∈ IN) ist nur dann Primzahl, wenn n eine Zweierpotenz n = 2^{k} ist. Falls F_{k} = 2^{2^{k}} + 1 eine Primzahl ist, heißt es Fermatsche Primzahl. (Es ist nicht bekannt, ob es unendlich viele Fermatsche Primzahlen gibt.)

(c) Für n ∈ IN gilt (∏_{ν=1}^{n−1} F_{ν}, F_{n}) = 1. Zeigen Sie daraus, daß es unendlich viele Primzahlen gibt.

* (d) Wann kann 4^{n} + 2^{n} + 1 eine Primzahl sein?

Aufgabe 4 (6 Punkte) Man beweise die folgenden Aussagen bzw. weise mit einem Gegenbeispiel nach, daß sie falsch sind: (Hierbei seien a, b, c ∈ IN, p ∈ IP.)

(a) (a, b) = (a, c) ⇒ (a^{2}, b^{2}) = (a^{2}, c^{2})

(b) (a, b) = (a, c) ⇒ (a, b) = (a, b, c)

(c) (a, b, c) = ((a, b), (a, c))

(d) (a, b) = 1 ⇒ (a^{2}, ab, b^{2}) = 1

(e) p | a ∧ p | (a^{2} + b^{2}) ⇒ p | b

(f) p | a^{7} ⇒ p | a

(g) a^{3} | c^{3} ⇒ a | c

(h) a^{3} | c^{2} ⇒ a | c

(i) a^{2} | c^{3} ⇒ a | c

(j) p | (a^{2} + b^{2}) ∧ p | (b^{2} + c^{2}) ⇒ p | (a^{2} − c^{2})

(k) p | (a^{2} + b^{2}) ∧ p | (b^{2} + c^{2}) ⇒ p | (a^{2} + c^{2})

(l) b | (a^{2} + 1) ⇒ b | (a^{4} + 1)

(m) b | (a^{2} − 1) ⇒ b | (a^{4} − 1)

Aufgabe 5 (4 Punkte) Sei p Primzahl. Zeigen Sie:

(a) Für n ∈ IN_{0} ist die Vielfachheit von p in n!

ν_{p}(n!) = ∑_{i=1}^{∞} ⌊\frac{n}{p^{i}} ⌋

* (b) Für m, n ∈ IN_{0} ist ν_{p} (\binom{m+n}{n}) gleich der Anzahl der Überträge, die beim Addieren von m und n im Ziffernsystem der Basis p auftreten.

Aufgabe 6 (5 Punkte) Der euklidische Algorithmus liefert zu a, b ∈ IN_{0} den ggT g = (a, b). Folgende Variante liefert auch eine Darstellung g = u · a + v · b mit u, v ∈ ZZ, und zwar fast immer mit kleinstmöglichem |u| und kleinstmöglichem |v|:

Seien a, b ∈ IN_{0} gegeben. Man betrachtet Tripel (x, y, z) mit x · a + y · b = z, x ∈ ZZ, y ∈ ZZ, z ∈ IN_{0} . Man startet mit (x_{1}, y_{1}, z_{1}) = (1, 0, a) und (x_{2}, y_{2}, z_{2}) = (0, 1, b). Für n = 2, 3, …: Falls z_{n} > 0, dividiere man z_{n−1} durch z_{n} mit Rest: z_{n−1} = q·z_{n}+z_{n+1} und setze (x_{n+1}, y_{n+1}, z_{n+1}) := (x_{n−1}, y_{n−1}, z_{n−1}) − q · (x_{n}, y_{n}, z_{n}). Falls z_{n} = 0, breche man ab, setze m := n und liefere (x_{m−1}, y_{m−1}, z_{m−1}) als Ergebnis.

z_{m−1} = g ist aus der Vorlesung bekannt.

(a) Finden Sie u, v mit u · a + v · b = (a, b), wobei a = 279, b = 191 bzw. a = 123456 und b Ihre Matrikelnummer sei.

(b) Zeigen Sie: Für das Ergebnis (u, v, g) = (x_{m−1}, y_{m−1}, z_{m−1}) gilt g = (a, b) ≥ 0, u · a + v · b = g. Falls b = 0: m = 2, (u, v, g) = (1, 0, a). Falls b > 0 und b | a: m = 3, (u, v, g) = (0, 1, b). Falls b > 0 und b |̸ a: m > 3, g > 0, |u| ≤ \frac{b}{2g}, |v| ≤ \frac{a}{2g}. (Hinweise: Untersuchen Sie die Vorzeichen von x_{n} und y_{n}. Was passiert mit den Ausdrücken x_{n} · y_{n+1} − x_{n+1} · y_{n}, x_{n} · z_{n+1} − x_{n+1} · z_{n}, y_{n} · z_{n+1} − y_{n+1} · z_{n} beim Schritt von n − 1 auf n? Setzen Sie dann n = m − 1 ein. )

* Aufgabe 7 (6 Punkte) Zeigen Sie: Für n ∈ IN ist die Gleichung

\frac{4}{n} = \frac{1}{x} + \frac{1}{y}

genau dann in natürlichen Zahlen x, y lösbar, wenn n einen Primteiler hat, der nicht von der Form p = 4k+1 ist.

Abgabe: Bis spätestens Donnerstag, 10.5.1990, 15.30 Uhr in den Kasten bei Zi. 308 des Mathematikgebäudes oder in der Übung im Hörsaal Hauptbau.