Fibonacci

Een toepassing:

Onder een getal verstaan we hier een positief geheel getal.
We stellen ons de volgende vraag: Welke getallen kunnen geschreven worden als som van precies 2 kwadraten.
Stelling: Als k² + 1 deelbaar is door n (voor een zekere k), dan kan n geschreven worden als som van precies 2 kwadraten.
Voorbeeld: 5² + 1 = 26 is deelbaar door 13, dus 13 is de som van precies 2 kwadraten. (13 = 2² + 3²).
Bewijs:
We nemen dus aan dat k² + 1 deelbaar is door n. (We veronderstellen k< n. Dat is altijd mogelijk omdat als k² + 1 deelbaar is door n, dan is ook (k-n)² + 1 deelbaar door n, enz.)
Voor het Fareyrijtje waarin alle noemers kleiner zijn dan n geldt dat het getal k/n ergens tussen twee breuken uit het Fareyrijtje ligt, zeg a'/b' en a/b.
Nu ligt (a'+a')/(b'+b) niet in dat Fareyrijtje, want (a'+a')/(b'+b) ligt tussen de naaste buren a'/b' en a/b, dus b'+b > n. Nu ligt k/n tussen a'/b' en (a'+a')/(b'+b) of tussen (a'+a')/(b'+b) en a/b.
Het maakt voor het vervolg niet uit welk van beide geldt, dus nemen we aan dat k ligt tussen (a'+a')/(b'+b) en a/b.
Dan is |k/n - a/b| ≤ |(a'+a)/(b'+b) - a/b| = {{onder 1 noemer brengen}} = |ba' - b'a|/(b(b'+b)) =
{a/b en a'/b' zijn buren, dus ab'-ba'=-1}} = 1/(b(b'+b)) ≤ 1/(bn).
Dus {{met nb vermenigvuldigen}} |kb - na| ≤ n.

Voor c = |kb - na| geldt dus 0 < c < n.
Ook voor b geldt {{b is een noemer uit het [n]-de Fareyrijtje}} 0 < b < n.
Dus 0 < b² + c² < 2n.
Als nu ook nog geldt dat b² + c² deelbaar is door n, dan hebben we aangetoond dat n = b² + c² en we zijn klaar.
Nu is b² + c² = b² + (kb - na)² = b² + k²b² - 2kbna + n²a² = b²(k² + 1) + n(-2kba + na²) en elke term is deelbaar door n (want k² + 1 is deelbaar door n).


We merken nog even op dat uit het bewijs ook nog volgt b en c geen gemeenschappelijke deler hebben, want
n = b²(k² + 1) + n(-2kba + na²) = b²(k² + 1) + na(-kb +/- c), dus 1 = b²{(k² + 1)/n} + a(-kb +/- c).
Hieraan zie je dat als q een deler is van zowel b als c, dan is q een deler van 1, dus q=1.

Voor de volledigheid bewijzen we nog even de omkering van bovenstaande stelling:
Is n = b² + c² en ggd(b,c)=1, dan is n een deler van k² + 1 voor zekere k.
Bewijs:
Als r een deler is van zowel c als n, dan is (daar n = b² + c²) r automatisch ook een deler van b, en dus is r=1.
Als we de resten bekijken bij deling door n van het rijtje 1.c, 2.c, 3.c, ..., n*c, dan levert dat een rijtje van alle n verschillende resten, want als bijvoorbeeld de rest van r.c bij deling door n gelijk is aan die van t.c, dan is r.c - t.c deelbaar door n, en daar n en c geen gemeenschappelijke deler hebben is dus r - t deelbaar door n, en dat is onmogelijk want 0 < r - t < n.
Dus een van de resten is 1 (zeg rest(u.c)). Dan is uc-1 deelbaar door n en nu² = u²(b² + c²) = (ub)² + (uc)² = (ub)² + (uc-1)(uc+1) + 1, en dus is n een deler van (ub)² + 1. qed