Fibonacci

An application:

In this text a number will allways be a positive integer.
We will answer the following question: Which numbers can be written as a sum of exactly 2 squares.
Theorem: If n divides k² + 1 (for certain k), then n can be written as a sum of exactly 2 squares.
Example: 13 divides 5² + 1 = 26, thus 13 is a sum of exactly 2 squares. (13 = 2² + 3²).
Proof:
We suppose that n divides k² + 1. (We assume k< n. That is allways possible for if n divides k² + 1, then n divides (k-n)² + 1 too, etc.)
For the Farey sequence in which all denominators are smaller than n, the number k/n is a number somewhere between two fractions from the Farey sequence, say a'/b' and a/b.
Now (a'+a')/(b'+b) is not a member of that Farey sequence, because (a'+a')/(b'+b) is put between the adjacent numbers a'/b' and a/b, so b'+b > n. The fraction k/n is situated between a'/b' and (a'+a')/(b'+b) or between (a'+a')/(b'+b) and a/b.
Without loss of generality we assume that k lies between (a'+a')/(b'+b) and a/b.
Then |k/n - a/b| ≤ |(a'+a)/(b'+b) - a/b| = {{we want 1 denominator}} = |ba' - b'a|/(b(b'+b)) =
{a/b and a'/b' are adjacent, so ab'-ba'=-1}} = 1/(b(b'+b)) ≤ 1/(bn).
Thus {{multiply by nb}} |kb - na| ≤ n.

For c = |kb - na| we have 0 < c < n.
Also for b we have {{b is a denominator from the [n]-th Farey sequence}} 0 < b < n.
Ergo 0 < b² + c² < 2n.
When also n divides b² + c², then we have shown that n = b² + c² and we are ready.
Now b² + c² = b² + (kb - na)² = b² + k²b² - 2kbna + n²a² = b²(k² + 1) + n(-2kba + na²) and n divides each term (for n divides k² + 1).


We notice that the proof also shows that b and c do not have a common factor, because
n = b²(k² + 1) + n(-2kba + na²) = b²(k² + 1) + na(-kb +/- c), so 1 = b²{(k² + 1)/n} + a(-kb +/- c).
This shows that if q divides b as well as c, then q divides 1, so q=1.

For the sake of completeness we now proof the inverse theorem:
If n = b² + c² and gcd(b,c)=1, then n divides k² + 1 for certain k.
Proof:
If r divides c as well as n, then (because n = b² + c²) r divides b, and thus r=1.
If we consider the remainders (after division by n) of the sequence 1.c, 2.c, 3.c, ..., n*c, then this yields a sequence of all n different remainders, because if for example the remainder of r.c equals the remainder of t.c, then n divides r.c - t.c, but n and c do not have a common divisor, thus n divides r - t. But that is impossible because 0 < r - t < n.
Therefore, one of the remainders is 1 (say remainder(u.c)). Then n divides uc-1 and nu² = u²(b² + c²) = (ub)² + (uc)² = (ub)² + (uc-1)(uc+1) + 1, and therefore n divides (ub)² + 1. qed