Dziś jeszcze jedna ciekawostka ze świata liczb Fibonacciego. Tym razem zamiast mówić o trójkątach pitagorejskich opowiemy trochę o największych wspólnych podzielnikach.

Otóż okazuje się, że dwie dowolnie wybrane liczby Fibonacciego mają następującą własność:

Największy wspólny podzielnik tych dwóch liczb jest jednocześnie liczbą Fibonacciego znajdującą się na pozycji odpowiadającej największemu wspólnemu podzielnikowi ich indeksów!

Poniatno?

Nie poniatno?

No to jeszcze raz, powoli:

Bierzemy n-tą liczbę Fibonacciego (Fn).

Bierzemy m-tą liczbę Fibonacciego(Fm).

Wyznaczamy największy wspólny dzielnik tych dwóch liczb.

W wyniku dostaniemy liczbę Fibonacciego znajdującą się na pozycji największego wspólnego podzielnika liczb m i n.

Poniatno?

Nie poniatno?

No to jeszcze raz, na konkretnym przykładzie:

Weźmy sobie szóstą z kolei liczbę Fibonacciego:

F6 = 8

Weźmy dziewiątą liczbę Fibonacciego:

F9 = 34

Największy wspólny dzielnik liczb 8 i 34 wynosi 2.

2 to trzecia liczba Fibonacciego.

Trzecia.

Trójka jest największym wspólnym podzielnikiem liczb 6 i 9.

Poniatno?

Nie poniatno?

Jeszcze jeden przykład w takim razie:

Bierzemy dwunastą liczbę Fibonacciego:

F12 = 144

Bierzemy szesnastą liczbę Fibonacciego:

F16 = 987

Największy wspólny podzielnik liczb 144 i 987...

...liczu, liczu, liczu...

... rozkładamy 144 na czynniki pierwsze: 144=22223*3

... rozkładamy 987 na czynniki pierwsze: 987 = 3747

Jak widać największy wspólny dzielnik 144 i 987 wynosi 3.

3 to czwarta z kolei liczba Fibonacciego.

Czwarta.

Największy wspólny podzielnik liczb 12 i 16 to właśnie 4.

Poniatno?

Nie poniatno?

To ja już prościej nie umię. Do pługa mi trza, albo rowy kopać...

Jeżeli ktoś chciałby zrozumieć skąd się taka zależność bierze, musiałby skorzystać z czterech innych twierdzeń, które mówią:

1. Dwie dowolne sąsiadujące ze sobą liczby Fibonacciego nie mają wspólnych podzielników poza jedynką.

2. Liczba Fibonacciego na pozycji (m+n), czyli Fm+n równa jest Fm+1 Fn + Fm Fn-1

3. Jeżeli m dzieli się przez n, wówczas m-ta liczba Fibonacciego dzieli się przez n-tą.

4. Jeżeli n = qm + r wówczas największy wspólny dzielnik liczb n i m jest równy największemu wspólnemu dzielnikowi liczb m i r.

Jak się te cztery twierdzenia złoży razem do tak zwanej kupy to Wyjdzie. A jak konkretnie to już mi się nie chce teraz tłumaczyć. Zaciekawionych odsyłam tutaj: https://www.math.hmc.edu/funfacts/ffiles/20004.5.shtml

Żeby było zabawniej, powyższa właściwość par liczb Fibonacciego może posłużyć do przeprowadzenia jednego z pierdylionów dowodów na to, że istnieje nieskończenie wiele liczb pierwszych.

Jeden z takich dowodów już kiedyś omawiałem: http://xpil.eu/numerki/

Tutaj sprawa jest dużo prostsza. Zaczynamy podobnie jak w tamtym dowodzie, a więc zakładamy, że liczb pierwszych jest k, a więc istnieje największa liczba pierwsza pk.

Weźmy teraz ciąg C liczb Fibonacciego o indeksach równych kolejnym liczbom pierwszym: F2, F3, F5, F7 i tak dalej aż do Fpk

Z omawianego wcześniej twierdzenia wynika, że dowolnie dwie wybrane z tego ciągu liczby będą miały tylko jeden wspólny podzielnik: jedynkę (bo ich indeksy są pierwsze, a więc dwa dowolnie wybrane indeksy będą miały jedynkę za największy wspólny dzielnik).

Skoro mamy tylko k liczb pierwszych, wówczas każda liczba Fibonacciego z tego ciągu powinna mieć tylko jeden podzielnik pierwszy (skoro są one wszystkie względnie pierwsze, nie mogą mieć wspólnych podzielników, a pamiętajmy, że kończą się one na liczbie Fpk.

Jednakowoż dziewiętnasta z kolei liczba Fibonacciego ma dwa podzielniki pierwsze: F19 = 4181 = 37 * 113.

Zgadza się?

A gówno, nie zgadza się, bo na początku ciągu Fibonacciego są dwie jedynki, a więc żeby obalić naszą tezę o skończonej ilości liczb pierwszych potrzebujemy co najmniej TRZECH podzielników pierwszych dla pewnego Fp. Na szczęście znajdujemy dobry przykład dla p = 37: F37 = 24157817 = 73 * 149 * 2221

Istnienie tej liczby oznacza, że albo twierdzenie Fibonacciego (omówione wcześniej) jest fałszywe, albo fałszywe jest założenie o skończonej ilości liczb pierwszych.

Skoro twierdzenie jest prawdziwe, w takim razie fałszywe musi być początkowe założenie. A więc liczb pierwszych jest nieskończenie wiele.

Ha!

Ten wpis jest luźnym tłumaczeniem tego oto artykułu: http://www.johndcook.com/blog/2017/01/17/infinite-primes-via-fibonacci-numbers/

This entry is a loose translation of http://www.johndcook.com/blog/2017/01/17/infinite-primes-via-fibonacci-numbers/