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

Elementare Zahlentheorie

Diese Aufgaben werden in der Übungsstunde vom 10.11.1999 besprochen; Abgabe schriftlicher Lösungen bitte am Montag, 8.11.1999, vor der Vorlesung.

1. Zeigen Sie, daß die diophantische Gleichung 4655 x + 12075 y = 805 lösbar ist, und bestimmen Sie sämtliche Lösungen.

2. Wie viele Möglichkeiten gibt es, ein Markstück in 50 - , 10 - und 5 - Pfennigstücke zu wechseln? Können Sie ein allgemeines Verfahren hierfür beschreiben?

3. (a) Es seien a, b, c, d ∈ ℤ, a^{2} + b^{2} + c^{2} > 0. Zeigen Sie, daß die diophantische Gleichung ax + by + cz = d genau dann lösbar ist, wenn (a, b, c) | d gilt.

(b) Lösen Sie die diophantische Gleichung

1819 x + 3587 y + 170 z = d , wobei d := (1819, 3587, 170).

4. Es sei 2 ≤ a ∈ ℕ und A_{n} := a^{2^{n}} + 1 für n ∈ ℕ.

(a) Bestimmen Sie (A_{m} , A_{n}) für alle m, n ∈ ℕ mit m < n.

(b) Zeigen Sie mit Hilfe von (a), daß es unendliche viele Primzahlen gibt.

5. (a) Berechnen Sie mit dem Euklidischen Algorithmus ggT (13, 8). Bestimmen Sie eine Linearkombination mit ggT (13, 8) = 13a + 8b und a, b ∈ ℤ.

(b) Zeigen Sie, daß für die Anzahl m(a, b) der Schritte im Euklidischen Algorithmus mit geeigneten positiven Konstanten c_{1}, c_{2} gilt:

c_{1} log x ≤ max_{1≤b≤a≤x} m(a, b) ≤ c_{2} log x .

Können Sie (ohne Beweis) angeben, wie gut man diese Konstanten für großes x wählen kann?