Übungen

Übung 1

(a)

Welche der Zahlen 2n − 1 für n = 2, …, 11 sind prim und welche nicht?

(b)

Zeigen Sie: Ist n ≥ 2 und p = 2n − 1 prim, so ist n prim.

[ Hinweis: ak − 1 = (ak − 1 + ak − 2 + … + a1 + a0) (a − 1) ]

(c)

Zeigen Sie: Sind a, n ≥ 2 und ist an − 1 prim, so ist a = 2 (und n prim).

Die Zahlen Mn = 2n − 1, n ≥ 1, heißen Mersenne-Zahlen. Ist eine Mersenne-Zahl Mn prim, so heißt Mn eine Mersenne-Primzahl. Es ist ein offenes Problem, ob es unendlich viele Mersenne-Primzahlen gibt. Der Leser konsultiere auch www.mersenne.org.

Übung 2

(a)

Erstellen Sie eine Tabelle, die alle Primzahlen kleiner als 100 in Primzahlen p mit p ≡  1 (4) und p ≡  3 (4) unterteilt.

(b)

Zeigen Sie, dass es unendlich viele Primzahlen p gibt mit p ≡  3 (4).

[ Hinweis: Betrachten Sie a = 2 · 2 · p1 · … · pn − 1 und orientieren Sie sich am Beweis der Unendlichkeit der Menge der Primzahlen von Euklid. Dass es unendlich viele Primzahlen p mit p ≡  1 mod(4) gibt, ist schwieriger zu zeigen. Wir geben später einen Beweis mit Hilfe des Satzes von Fermat. ]

Übung 3

Zeigen Sie, dass für alle a, d mit d ≠ 0 gilt: 

d | a  genau dann, wenn  ∀p prim exp(d)  ≤  exp(a)

Übung 4

Geben Sie eine Formel für die Anzahl τ(n) der Teiler d ≥ 1 einer natürlichen Zahl n ≥ 1 an und beweisen Sie diese Formel.

Übung 5

(a)

Berechnen Sie für einige m, k ≥ 1 Summen der Form

m  +  (m + 1)  +  …  +  (m + k).

(b)

Formulieren Sie eine Hypothese, welche Zahlen n ≥ 1 sich als Summen wie in (a) darstellen lassen (mit mindestens zwei Summanden).

(c)

Beweisen Sie Ihre Hypothese.

Übung 6

Berechnen Sie für einige Primzahlen p dasjenige r  ∈  { 0, …, p − 1 } mit

(p − 1)!  ≡   r  (p).

Stellen Sie eine allgemeine Hypothese auf und versuchen Sie diese zu beweisen.

[ Hinweis: Paarbildung mit Zahlen a, b mit a b ≡  1 (p). ]

Übung 7

Sei n ≥ 6 eine zusammengesetzte Zahl. Zeigen Sie, dass

(n − 1)!  ≡   0  (n).

Übung 8

Sei p eine Primzahl mit p ≡  1 (3). Zeigen Sie, dass p ≡  1 (6).

Übung 9

Sei n ≥ 1. Zeigen Sie, dass eine drei Zahlen n, n + 2, n + 4 durch 3 teilbar ist, sodass es mit Ausnahme von (3, 5, 7) keinen Primzahldrilling der Form (p, p + 2, p + 4) geben kann.

Übung 10

Ein alternativer Beweis der Unendlichkeit der Menge der Primzahlen:

Für jedes n ≥ 0 sei Fn = 22n + 1 die n-te Fermat-Zahl.

(a)

Seien 0 ≤ m < n. Zeigen Sie, dass Fm | (Fn − 2).

(b)

Seien 0 ≤ m < n. Zeigen Sie mit Hilfe von (a), dass Fm und Fn keine gemeinsamen Teiler d ≥ 2 besitzen.

(c)

Folgern Sie aus (b), dass es unendlich viele Primzahlen gibt.

[ Hinweis zu (a): Verwenden Sie, dass (Fn − 2)/Fm = (ak − 1)/(a + 1)  ∈  ℕ für gewisse a ≥ 1 und k ≥ 2, k gerade. Alternativ: Zeigen Sie durch Induktion, dass Fn = F0 … Fn − 1 + 2 für alle n ≥ 1. ]

Ist eine Fermat-Zahl Fn prim, so heißt Fn eine Fermat-Primzahl. Die Fermat-Zahlen

F0  =  3,  F1  =  5,  F2  =  17,  F3  =  257,  F4  =  65537

sind prim. Weitere Fermatsche-Primzahlen sind nicht bekannt. Beispielsweise gilt

F5  =  4294967297  =  641 · 6700417.

Es ist ein offenes Problem, ob es unendlich viele Fermat-Primzahlen gibt.