Fibonacci

Eine Anwendung:

Eine Zahl ist hier immer eine positive ganze Zahl.
Wir stellen uns die nächste Frage: Welche Zahlen können dargestellt werden als Summe von genau 2 Quadraten.
Satz: Wenn n ein Teiler ist von k² + 1 (für gewisses k), dann ist n als Summe von genau 2 Quadraten darstellbar.
Beispiel: 13 teilt 5² + 1 (= 26), also ist 13 die Summe von genau 2 Quadraten. (13 = 2² + 3²).
Beweis:
Es sei n teiler von k² + 1. (Wir nehmen an dass k< n. Wenn das nicht der Fall ist, dann können wir so oft n von k substrahieren bis das Resultat kleiner is als n, denn wenn n, k² + 1 teilt, dann teilt n auch (k-rn)² + 1 für jedes r).
Für die Fareyreihe mit Nennern kleiner als n gilt, dass die Zahl k/n irgendwo zwischen zwei Brüchen der Fareyreihe liegt, sage zwischen a'/b' und a/b.
Nun befindet sich (a'+a')/(b'+b) nicht in dieser Fareyreihe, denn (a'+a')/(b'+b) liegt zwischen den Nachbarn a'/b' und a/b, also b'+b > n. Nun liegt k/n zwischen a'/b' und (a'+a')/(b'+b) oder zwischen (a'+a')/(b'+b) und a/b.
Ohne Beschränkung der Allgemeinheit nehmen wir an dass k liegt zwischen (a'+a')/(b'+b) und a/b.
Dann ist |k/n - a/b| ≤ |(a'+a)/(b'+b) - a/b| = {{unter 1 Nenner bringen}} = |ba' - b'a|/(b(b'+b)) =
{a/b und a'/b' sind Nachbarn, also ab'-ba'=-1}} = 1/(b(b'+b)) ≤ 1/(bn).
Also {{mit nb multiplizieren}} |kb - na| ≤ n.

Für c = |kb - na| gilt also 0 < c < n.
Auch für b gilt {{b ist ein Nenner aus der <n-ten Fareyreihe}} 0 < b < n.
Also 0 < b² + c² < 2n.
Wenn nun auch noch gilt dass n, b² + c² teilt, dann haben wir gezeigt dass n = b² + c² und wir sind fertig.
Nun ist b² + c² = b² + (kb - na)² = b² + k²b² - 2kbna + n²a² = b²(k² + 1) + n(-2kba + na²) und n teilt jeden Term (denn n teilt k² + 1).


Wir bemerken noch dass aus dem Beweis auch noch folgt dass b und c teilerfremd sind, denn
n = b²(k² + 1) + n(-2kba + na²) = b²(k² + 1) + na(-kb +/- c), also 1 = b²{(k² + 1)/n} + a(-kb +/- c).
Das zeigt dass wenn q, b und c teilt, dann teilt q, 1, also q=1.

Wir beweisen jetzt noch die Umkehrung des obenerwähnten Satzes:
Wenn n = b² + c² und b und c sind teilerfremd, dann teilt n k² + 1 für gewisses k.
Beweis:
Wenn r sowohl c als auch n teilt, dann (da n = b² + c²) teilt r auch b, und dann is r=1.
Wenn wir die Zahlen der Reihe 1.c, 2.c, 3.c, ..., n*c teilen durch n, dann gibt das eine Reihe von n verschiedenen Resten, denn wenn zum Beispliel der Rest von r.c bei einer Teilung durch n gleich dem Rest von t.c ist, dann teilt n sicher r.c - t.c, und da n und c teilerfremd sind teilt n, r - t, und das ist unmöglich denn 0 < r - t < n.
Also ist einer der Reste gleich 1 (sage Rest(u.c)). Dann teilt n uc-1 und nu² = u²(b² + c²) = (ub)² + (uc)² = (ub)² + (uc-1)(uc+1) + 1, und folglich teilt n (ub)² + 1. qed