Lösungshinweise zu Übungsblatt 3

Universität Würzburg
Mathematisches Institut
Dr. J. Jordan, L. Lauerbach
28.04.2016
3 . Übung zur Zahlentheorie
Abgabe: Bis 12.05.2016, 10.14 Uhr, in der Vorlesung.
3.1 Bestimmen Sie alle Fibonacciprimzahlen der Form 4k + 3, k ∈ N0 . Hinweis: Zeigen
2
Sie zunächst die Formel f2n−1 = fn2 + fn−1
, n ∈ N.
Lösungshinweise:
Wir zeigen zuerst die im Hinweis angegebene Formel. Aus der Vorlesung ist bekannt, dass
fr+s = fr−1 fs + fr fs+1 gilt. Dies wollen wir auf f2n−1 anwenden:
2
f2n−1 = fn+(n−1) = fn−1 fn−1 + fn fn = fn2 + fn−1
∀n ∈ N.
(1)
Zunächst einmal stellen wir fest, dass für k = 0 die Zahl 4k + 3 = 3 = f4 eine Fibonacciprimzahl ist. Des Weiteren wissen wir aus der Vorlesung, dass für eine Fibonacciprimzahl
fm mit m > 4 gelten muss, dass m eine Primzahl ist (da gilt fm teilt fkm ). Insbesondere
muss also für eine Fibonacciprimzahl fm gelten, dass m ungerade ist, also m = 2n − 1.
Diese Fibonacciprimzahl f2n−1 kann jedoch wie in Gleichung (1) gezeigt, als Summe zweier Quadratzahlen geschrieben werden, es muss also gelten 4k + 3 = f2n−1 = a2 + b2 für
a, b ∈ N geeignet. Eine Zahl der Form 4k + 3 kann jedoch nicht als Summe von zwei
Quadratzahlen geschrieben werden. Die sieht man wie folgt:
a gerade b gerade
a ungerade b ungerade
a gerade b ungerade
a ungerade b gerade
:
:
:
:
a2 + b 2
a2 + b 2
a2 + b 2
a2 + b 2
= (2m)2 + (2m)2 = 8m2 ≡ 0 mod 4
= (2m + 1)2 + (2m + 1)2 = 8m2 + 8m + 2 ≡ 2 mod 4
= (2m)2 + (2m + 1)2 = 8m2 + 4m + 1 ≡ 1 mod 4
= (2m + 1)2 + (2m)2 = 8m2 + 4m + 1 ≡ 1 mod 4
Die Summe zweier Quadrate modulo 4 ist also niemals kongruent zu 3, was sie aber sein
müsste, wenn 4k + 3 ≡ 3 mod 4 eine Fibonacciprimzahl sein soll. Somit gibt es außer
f4 = 3 keine weitere Fibonacciprimzahl der Form 4k + 3.
3.2 (Aus einem Schülerwettbewerb)
Für die Zahlenfolge a0 , a1 , a2 , . . . gelte:
a0 = 0, a1 = a2 = 1, und an+2 + an−1 = 2(an+1 + an ).
Zeigen Sie, dass alle Folgenglieder dieser Folge Quadratzahlen sind.
Lösungshinweise:
Wir berechnen zunächst ein paar Beispiele:
a0 = 0 = 0 2
a1 = 1 = 1 2
a2 = 1 = 1 2
a3 = 4 = 2 2
a4 = 9 = 3 2
a5 = 25 = 52
a6 = 64 = 82
a7 = 169 = 132
...
Zuerst einmal sieht man, dass die Behauptung vermutlich stimmt, nämlich dass alle Folgenglieder Quadratzahlen sind. Man sieht sogar noch mehr, es sind nicht beliebige Quadratzahlen, sondern jeweils Quadrate der Fibonaccizahlen. Daher stellen wir folgende Vermutung auf: an = fn2 für n ∈ N. Dies zeigen wir mittels vollständiger Induktion(Beachte:
In diesem Fall benötigen wir eine Induktion mit drei Startwerten, da war von n − 2, n − 1
und n auf n + 1 schließen wollen. Dies wird klar in dem Schritt, bei dem im Induktionsschluss die Induktionsbehauptung für drei vorherige Folgenglieder eingesetzt wird.):
I.A.: Für n = 1 gilt a1 = 1 = 12 = f12 , für n = 2 gilt a2 = 1 = 12 = f22 und für n = 3 gilt
a3 = 4 = 22 = f32
I.B.: an = fn2 gilt für drei aufeinanderfolgende n ∈ N.
I.S.: ”(n − 2, n − 1, n) → n + 1”:
an+1
Rekursion
=
2(an + an−1 ) − an−2
I.B.
2
2
= 2(fn2 + fn−1
) − fn−2
Rekursion
2
2
=
2((fn−1 + fn−2 )2 + fn−1
) − fn−2
2
2
= 4fn−1
+ 4fn−1 fn−2 + fn−1
= (2fn−1 + fn−2 )2
= (fn−1 + fn−1 + fn−2 )2
Rekursion
(fn−1 + fn )2
Rekursion
(fn+1 )2
=
=
Damit ist die Behauptung, dass alle Folgenglieder Quadratzahlen sind für n ∈ N gezeigt.
Es fehlt also noch die Behauptung für n = 0, welche jedoch leicht nachzurechnen ist:
a0 = 0 = 02 , a0 ist also auch eine Quadratzahl.
3.3 Sind p und 2p + 1 beides Primzahlen, so nennt man p eine Germain Primzahl.
a) Bestimmen Sie alle Germain Primzahlen, die auch Mersenne Primzahlen sind.
b) Bestimmen Sie alle Germain Primzahlen, die auch Fermat Primzahlen sind.
c) Bestimmen Sie alle Germain Primzahlen, die auch Euklidische Primzahlen sind.
Lösungshinweise:
Wir zeigen zunächst folgende Aussage: Ist p > 3 eine Germain Primzahl, so ist p = 6k − 1
für ein k ∈ N.
Beweis: Wir betrachten alle Restklassen modulo 6: Ist p ≡ 0 mod 6, oder p ≡ 2 mod 6
oder p ≡ 4 mod 6 so ist p durch 2 teilbar, also keine Primzahl für p > 3. Ist p ≡ 3
mod 6, so ist p durch 3 teilbar und auch keine Primzahl für p > 3. Ist p ≡ 1 mod 6, so
ist 2p + 1 = 2(6n + 1) + 1 = 12n + 3 durch 3 teilbar, also ist p keine Germain Primzahl.
Es bleibt also für Germain Primzahlen nur der Fall p ≡ 5 ≡ −1 mod 6.
a) Es sei p ∈ M ∩ G. Da p ∈ M ist, gilt p = 2q − 1 mit q ∈ P. Wegen p ∈ G gilt für alle
p > 3, dass p = 6k − 1 für ein k ∈ N ist. Daher betrachten wir zuerst die (darin nicht
enthaltenen) Fälle p = 2 und p = 3 einzeln:
Für p = 2 gilt: 2 ∈
/ M , da 2 = 2q − 1 ⇔ 3 = 2q nicht lösbar.
Für p = 3 gilt: 3 = 22 − 1, also 3 ∈ M , und außerdem ist 2 · 3 + 1 = 7 ebenfalls eine
Primzahl, also 3 ∈ G. Somit gilt 3 ∈ G ∩ M
Nun zu p > 3: Wir setzen beide Terme für p gleich und dies ergibt 2q − 1 = 6k − 1. Addition der 1 und anschließend Division durch 2 liefert 2q−1 = 3k. Die linke Seite ist eine
Zweierpotenz und daher nicht durch 3 teilbar. Damit hat diese Gleichung keine Lösung
und es gilt G ∩ M = {3}.
m
b) Es sei p ∈ F ∩ G. Da p ∈ F ist, gilt p = 22 + 1 mit m ∈ N0 . Wegen p ∈ G gilt für
alle p > 3, dass p = 6k − 1 für ein k ∈ N ist. Daher betrachten wir zuerst die (darin nicht
enthaltenen) Fälle p = 2 und p = 3 einzeln:
m
m
Für p = 2 gilt: 2 ∈
/ F , da 2 = 22 + 1 ⇔ 1 = 22 nicht lösbar.
m
Für p = 3 gilt: 3 = 22 + 1 ⇔ m = 0, also 3 ∈ F . Ebenso gilt 3 ∈ P und 2 · 3 + 1 = 7 ∈ P,
also 3 ∈ G. Somit ist 3 ∈ F ∩ G.
m
Nun zu p > 3: Wir setzen beide Terme für p gleich und dies ergibt 22 + 1 = 6k − 1.
Addition der 1 und Division durch 2 ergibt
m −1
22
+ 1 = 3k.
(2)
Da der Fall m = 0 schon bei p = 3 abgehandelt wurde, können wir m ≥ 1 annehmen.
Damit folgt, dass k ungerade sein muss, da auf der linken Seite von (2) eine (gerade)
Zweierpotenz plus 1 steht, was ungerade ist. Daher setzen wir k = 2n − 1 für n ∈ N.
Eingesetzt in (2) ergibt das
m −1
22
m −1
+ 1 = 3(2n − 1) ⇔ 22
= 6n − 4 ⇔ 22
2(2m−1 −1)
⇔ 2
4
= 3n − 2
2m−1 −1
= 3n − 2 ⇔ 4
2m−1 −1
⇔ n=
m −2
= 3n − 2
+2
.
3
Dieses Ergebnis für n setzen wir nun in k = 2n − 1 und dann wiederum in p = 6k − 1 ein,
und erhalten
m−1 −1
p = 6(2n − 1) − 1 = 6 ·
= 42
2 · (42
m−1
3
+ 2)
m−1 −1
− 7 = 4 · (42
+ 2) − 7
+ 1.
Dies is zuerst einmal ein Ergebnis für p. Jetzt müssen wir noch überprüfen, ob 2p + 1 auch
m−1
eine Primzahl ist (damit p eine Germain Primzahl ist). Wir betrachten also 2(42 +1)+1.
Es gilt
m−1
m−1
m−1
2(42
+ 1) + 1 = 2 · 42
+ 3 ≡ 2 · (−1)2
+ 3 mod 5.
Solange m ≥ 2 ist, ist der Exponent 2m−1 gerade und es gilt
m−1
2 · (−1)2
+3=2·1+3=5≡0
mod 5.
Das heißt aber, dass 2p + 1 durch 5 teilbar ist, und somit keine Primzahl sein kann. Damit
ist auch p keine Germain Primzahl. Allerdings fehlt noch ein Fall, denn wir haben m ≥ 2
angenommen. Wir müssen also noch m = 1 einzeln betrachten (m = 0 ist schon bei p = 3
betrachtet worden):
m−1
+ 1 = 5 ∈ P und 2p + 1 = 11 ∈ P. Somit ist 5 ∈ G. Außerdem
Für m = 1 gilt: p = 42
1
ist 5 = 22 + 1 und somit ist 5 ∈ F .
Insgesamt also gilt F ∩ G = {3, 5}.
Q
c) Sei p ∈ E ∩ G. Da p ∈ E ist, gilt p = ki=1 pi + 1 mit pi ∈ P. Wegen p ∈ G ist p = 6k − 1
für ein k ∈ N und p > 3. Daher betrachten wir zuerst die (darin nicht enthaltenen) Fälle
p = 2 und p = 3 einzeln:
Q
Q
Für p = 2 gilt: 2 ∈
/ E, da 2 = ki=1 pi + 1 ⇔ 3 = ki=1 pi nicht lösbar.
Für p = 3 gilt: 3 ∈ E, da 2 + 1 = 3 und 3 ∈ G, da 2 · 3 + 1 = 7 auch eine Primzahl ist.
Somit ist 3 ∈ E ∩ G.
Q
Nun zu p > 3: Wir setzen beide Terme für p gleich und dies ergibt ki=1 pi + 1 = 6k − 1.
Qk
Subtraktion der 1 und anschließend Division durch 2 liefert i=2 pi = 3k − 1. Für diese
Gleichung existiert keine Lösung, was man wie folgt sieht:
k
Y
pi ≡ 0
mod 3 aber 3k − 1 ≡ 2
mod 3.
i=2
Da beide Seiten modulo 3 nicht übereinstimmen, kann es keine Lösung geben. Somit ist
E ∩ G = {3}.