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ą:
- Dwie dowolne sąsiadujące ze sobą liczby Fibonacciego nie mają wspólnych podzielników poza jedynką.
- Liczba Fibonacciego na pozycji (m+n), czyli Fm+n równa jest Fm+1 Fn + Fm Fn-1
- Jeżeli m dzieli się przez n, wówczas m-ta liczba Fibonacciego dzieli się przez n-tą.
- 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/
Wg mnie nie istnieje coś takiego jak ciąg Fibonacciego, Ba nie istnieją liczby. To człowiek je wymyślił, a de facto są tylko zależności – taka moja może szalona teoria. Ciąg Fibonacciego – może ciąg czegoś, zrobiłem sobie prosty test w arkuszu kalkulacyjnym, utworzyłem ciąg, czyli 1+1, 2+1, 3+2 itd. przeciągamy w dół – super! mamy ciąg Fibonacciego, dzielimy mniejszą przez większą i mamy liczbę Fi – wow 1,618033989, cóż wszystko super! Najlepsze, że cokolwiek nie podstawimy za dwie pierwsze jedynki to wynik dzielenia zawsze daje liczbę Fi, dlatego uważam, że liczby nie istnieją – a istnieją jedynie zależności, a liczby wymyślił człowiek aby wyobrazić “policzalność” ?
Tak BTW, to musi coś być w tym Fi, skoro natura nas otaczająca korzysta z tej zależności – galaktyki, rośliny etc.
Zastanawia mnie co stanowi istotę liczb pierwszych i ich zależności – bawię się dalej arkuszem ?
Jeśli chodzi o duże liczby pierwsze to polecam lekturę tego wpisu: https://xpil.eu/pchelki-python-test-millera-rabina/