Fibonacci

valentino · Messaggio da **valentino** » 01 gen 1970, 01:33

So che il problema se esistono infiniti primi nella successione di Fibonacci è aperto. Invece ho guardato quanti quadrati ci sono e dopo 1 e 144 non ne ho trovati (ho controllato fino ad un numero di circa 150 cifre). Qualcuno sa se si è dimostrato qualcosa in proposito? E per le altre potenze? <IMG SRC="images/forum/icons/icon_confused.gif">

lordgauss · Messaggio da **lordgauss** » 01 gen 1970, 01:33

Il problema 25 del giornalino n°4 è stata l\'occasione per approfondire sui numeri di Fibonacci: cercherò ora di spingermi un po\' più avanti recuperando questo vecchio post.
 
 Gli unici quadrati presenti nella serie sono F(1)=F(2)=1 e F(12)=144, mentre l\'unica altra potenza è F(6)=8.
 
 Diamo ora una parziale giustificazione della risposta.
 A tale scopo, consideriamo la tabella sottostante con le fattorizzazioni dei primi 15 numeri di Fibonacci.
 
 F(1)=1
 F(2)=1
 F(3)=2
 F(4)=3
 F(5)=5
 F(6)=8=2³
 F(7)=13
 F(<IMG SRC="images/forum/icons/icon_cool.gif">=21=3*7
 F(9)=34=2*17
 F(10)=55=5*11
 F(11)=89
 F(12)=144=2^4*3²
 F(13)=233
 F(14)=377=13*29
 F(15)=610=2*5*61
 ...
 
 Si vede subito come, fatta eccezione per F(6) e F(12), nella fattorizzazione di ogni numero di Fibonacci compaia un nuovo numero primo mai apparso nelle fattorizzazioni dei precedenti numeri di Fibonacci.
 Potremmo congetturare che F(6) e F(12) siano gli unici numeri che non sottostanno a questa regola, ed in effetti è proprio così: ciò è stato dimostrato sotto il nome di \"Teorema di Carmichael\" - o qualcosa del genere.
 Da qui risulta ovvio che F(6)=8 e F(12)=144 sono le uniche \"potenze di Fibonacci\".
 
 
 [addsig]

lordgauss · Messaggio da **lordgauss** » 01 gen 1970, 01:33

Naturalmente ciò che ho detto non è soddisfacente, perchè si rinvia il tutto ad un teorema forse ancora più difficile da dimostrare della proposizione originale.
 Perciò proverò a tratteggiare le linee di una dimostrazione, perlomeno per ciò che riguarda i quadrati.
 
 TESI: gli unici quadrati di Fibonacci sono F(1)=F(2)=1 e F(12)=144.
 
 Assumiamo anzitutto la tesi del problema 25 del giornalino, ovvero che F(MCD(n,m))=MCD(F(n),F(m)). Ovviamente non la si può dimostrare a meno di pubblico linciaggio.
 Sia ora F(m)=k² un quadrato di Fibonacci maggiore di 144. Dimostriamo che supporne l\'esistenza conduce ad un assurdo.
 
 CASO 1) m non è divisibile per 12.
 Abbiamo MCD(k²,144)=F(MCD(12,m)). Ma MCD(k²,144)<144 è anch\'esso un quadrato r² e dunque, poichè anch\'esso è un numero di Fibonacci, può valere solo F(1)=F(2)=1. Dunque MCD(12,m)=1 oppure 2 da cui si evince facilmente che m deve essere della forma 12s±1, 12s±2, 12s±5, ovvero della forma 6s±1, 6s±2.
 Analizzando le congruenze modulo F(6)=8 dei numeri di Fibonacci si vede come un numero del tipo F(12s±5) sia congruo a 5 modulo 8 e dunque non possa essere un quadrato. Lo stesso dicasi per i numeri del tipo F(12s-2).
 Se invece consideriamo le congruenze modulo F(12)=144 vediamo che non tutti i numeri del tipo F(12±1), F(12s+2) sono accettabili: solo quelli del tipo F(24s±1), F(24s+2) danno un resto accettabile.
 Se ora andiamo a considerare le congruenze modulo F(24)=46368 vediamo che sono accettabili sono i numeri del tipo F(48s±1), F(48s+2), e così via. Questo ragionamento può essere ripetuto tante volte quante vogliamo.
 Perciò il candidato F(m)=k² dopo la prima analisi deve essere maggiore di 6, dopo la seconda maggiore di 12, dopo la terza maggiore di 24, dopo la n-esima maggiore di 6*2^(n-1), con n grande a piacere.
 Pertanto non esiste nessun quadrato maggiore di 144 non divisibile per 144.
 NOTA: Le proposizioni sulle congruenze sono tutte facilmente dimostrabili, visto che anche nei numeri di Fibonacci le congruenze sono cicliche.
 
 CASO 2) m è divisibile per 12.
 Ecco, in apparenza questo secondo ed ultimo caso è facilmente risolvibile, ma proprio non ne vengo fuori.
 Pertanto lo propongo come problema aperto: AIUTO!