jordan ha scritto:Da
qui.
La successione degli $ \{f_i\}_{i \in \mathbb{N}} $ ha polinomio caratteristico $ p(x)=x^2-x-1 $; verificato che $ p(x) $ ha due radici distinte $ r_1 \neq r_2, (r_1,r_2) \in \mathbb{C}^2 $, esiste una coppia $ (\alpha_1,\alpha_2) \in \mathbb{R}^2 $ tale che $ f_i=\alpha_1r_1^i+\alpha_2r_2^i, \forall i \in \mathbb{N} $. Imposto il vincolo $ f_j=j $ per $ j \in \{0,1\} $ otteniamo la cosiddetta
formula di Binet:
- $ \displaystyle f_i= \frac{1}{\sqrt{5}} \left(\left(\frac{1}{2}(1+\sqrt{5}\;\!)\right)^i-\left(\frac{1}{2}(1-\sqrt{5}\;\!)\right)^i\right), \forall i \in \mathbb{N} $
Lemma 1. Essendo $ \mathbb{P}:=\{2,3,5,\ldots\} $ e $ e_p := \displaystyle \left(\frac{p}{5}\right) $, è vero che $ p^\alpha \mid \displaystyle f_{p^{\alpha-1}(p-e_p)} $, per ogni $ p \in \mathbb{P} \setminus \{2,5\} $ e $ \alpha \in \mathbb{N}_0 $. Qui $ \displaystyle \left(\frac{p}{5}\right) $ denota un
simbolo di Legendre.
Prova. Mostriamo la tesi per
induzione: essa è vera per $ \alpha=1 $, infatti operando in $ \mathbb{Z}/p\mathbb{Z}[\sqrt{5}\;\!] $, considerando che $ \displaystyle \left(\frac{p}{5}\right)=\left(\frac{5}{p}\right) $ e che $ 1 \pm\sqrt{5} $ è invertibile in $ \mathbb{Z}/p\mathbb{Z}[\sqrt{5}] $
se e solo se $ p>2 $ (v.
qui Lemma 1), vale (v.
qui,
extended FLT)
- $ (1+e_p\sqrt{5}\;\!)(1-\sqrt{5}\;\!)^{e_p} = (1-e_p\sqrt{5}\;\!)(1+\sqrt{5}\;\!)^{e_p} $ $ \implies (1+\sqrt{5}\;\!)^p(1-\sqrt{5}\;\!)^{e_p} = (1-\sqrt{5}\;\!)^p(1+\sqrt{5}\;\!)^{e_p} $ $ \implies p \mid \displaystyle f_{p-e_p} $.
Supponiamo che adesso la tesi sia valida per un qualche $ \alpha \in \mathbb{N}_0 $, allora è vera anche per $ \alpha+1 $.
Infatti per ipotesi avremo che $ \displaystyle (1+\sqrt{5}\;\!)^{p^{\alpha-1}(p-e_p)} = (1-\sqrt{5}\;\!)^{p^{\alpha-1}(p-e_p)} $ in $ \mathbb{Z}/p^\alpha\mathbb{Z}[\sqrt{5}\;\!] $, cioè esistono $ k_1,k_2,t_1,t_2 \in \mathbb{Z}/p\mathbb{Z} $ che verificano:
- $ \displaystyle (k_1+t_1\sqrt{5})p^\alpha+(1+\sqrt{5})^{p^{\alpha-1}(p-e_p)} $ $ = (k_2+t_2\sqrt{5})p^{\alpha}+(1-\sqrt{5})^{p^{\alpha-1}(p-e_p)} $ in $ \mathbb{Z}/p^{\alpha+1}\mathbb{Z}[\sqrt{5}] $,
Allora è vero che:
- $ \displaystyle \Big((k_1+t_1\sqrt{5})p^\alpha+(1+\sqrt{5})^{p^{\alpha-1}(p-e_p)}\Big)^p $ $ = \Big((k_2+t_2\sqrt{5})p^{\alpha}+(1-\sqrt{5})^{p^{\alpha-1}(p-e_p)}\Big)^p $ in $ \mathbb{Z}/p^{\alpha+1}\mathbb{Z}[\sqrt{5}] $,
Sennonché (v.
qui, lemma 2) per ogni $ 1 \le i \le p-1 $ risulta $ \displaystyle p \mid \binom{p}{i} $, per cui espandendo la relazione precedente risulta che:
- $ \displaystyle (1+\sqrt{5})^{p^{\alpha}(p-e_p)} = (1-\sqrt{5})^{p^{\alpha}(p-e_p)} $ in $ \mathbb{Z}/p^{\alpha+1}\mathbb{Z}[\sqrt{5}] $.
La verifica del passo di induzione è ora completa.
Lemma 2. Per ogni $ n \in \mathbb{N}_0 $ vale $ \displaystyle \upsilon_5(f_n)=\upsilon_5(n) $. In particolare $ \displaystyle \upsilon_5(f_{5^\alpha})=\alpha $ per ogni $ \alpha \in \mathbb{N} $. Qui $ \upsilon_5(\cdot) $ denota la
valutazione p-adica, con $ p=5 $.
Prova. Espandendo la formula di Binet e considerando che $ (2^n,5)=1, \forall n \in \mathbb{N}_0 $ abbiamo che $ \displaystyle \upsilon_5(f_n)=\upsilon_5\!\Bigg(\sum_{i = 0}^{\left\lfloor n/2\right\rfloor}C_n^{2i+1}5^i }\Bigg) $, dove $ \displaystyle C_n^{2i+1} := \binom{n}{2i+1} $, per ogni $ i=0, 1, \ldots, \left\lfloor n/2\right\rfloor $ (v.
qui). Sennonché se $ i>0 $ vale $ \displaystyle \upsilon_5(C_n^{2i+1} 5^i)= $ $ \displaystyle \upsilon_5\!\left(\frac{n}{2i+1}\right)+\upsilon_5(C_{n-1}^{2i}5^i) \ge $ $ \upsilon_5(n)+i-\upsilon_5(2i+1)>\upsilon_5(n) $, e ciò è sufficiente per mostrare il nostro lemma (si osservi che $ C_n^1 = n $).
Lemma 3. Per ogni $ \alpha \in \mathbb{N} \setminus \{0,1,2\} $ vale $ \displaystyle 2^{\alpha} \mid f_{3 \;\!\cdot\;\! 2^{\alpha-2}} $.
Prova. La tesi è banalmente vera per $ \alpha=3 $, siccome $ f_6 = 2^3 $. Ricordiamo inoltre che, dati $ (m,n) \in \mathbb{N}_0^2 $ vale (v.
qui)
- $ f_{m+n}=f_mf_{n-1}+f_nf_{m+1}\qquad \mbox{(*)} $
e in particolare, se $ m=n $ vale $ f_{2n}=f_n(f_{n+1}+f_{n-1}) $. Supponiamo, adesso, che la tesi sia vera per un certo $ \alpha $, dimostriamola per $ \alpha+1 $. Abbiamo che la successione degli $ \{f_i\}_{i \in \mathbb{N}} $ è periodica modulo 2 con periodo 3, e in particolare $ 2 \mid f_i $ se e solo se $ 3 \mid i $. Per cui, grazie alla $ \mbox{(*)} $, abbiamo $ \displaystyle 2^{\alpha+1} \mid f_{3\;\! \cdot\;\! 2^{\alpha-2}}(f_{3 \;\!\cdot\;\! 2^{\alpha-2}+1}+f_{3 \;\!\cdot \;\!2^{\alpha-2}-1})=f_{3 \;\!\cdot\;\! 2^{\alpha-1}} $, in quanto il primo fattore è multiplo di $ 2^{\alpha} $ per ipotesi, mentre il secondo è somma di due numeri dispari.
Possiamo anche facilmente osservare che grazie all'algoritmo delle divisione euclidea $ \gcd(f_x,f_y)=f_{\gcd(x,y)} $ per ogni $ x,y \in \mathbb{N} $. Segue quindi che $ f_x \mid f_y $ sse $ x \mid y $.
Definiamo $ g(\cdot): \mathbb{N} \to \mathbb{N} $ la funzione tale che:
- i) $ g(1)=1 $
ii) $ g(2)=3 $
iii) $ g(4)=6 $
iv) $ g(p^t)=p^{t-1}(p-e_p) $, per ogni $ p \in \mathbb{P} \setminus\{2\} $ e $ t \in \mathbb{N}_0 $, con $ \displaystyle e_p := \left(\frac{p}{5}\right) $.
v) $ g(2^t)=3 \cdot 2^{t-2} $, per ogni $ t \in \mathbb{N} \setminus \{0,1,2\} $
vi) $ g(xy)=\mbox{lcm}\big(g(x),g(y)\big) $, per ogni $ x,y \in \mathbb{N}_0 $.
Mostriamo che la funzione $ g(\cdot) $ soddisa le ipotesi del problema: $ n \mid f_{g(n)} $ e $ g(n) \le 2n, \forall n \in \mathbb{N}_0 $.
Dato che $ f_x \mid f_y $ se e solo se $ x \mid y $, grazie ai lemmi 1,2,3, e alla definizione della funzione $ g(\cdot) $ vale $ n \mid f_{g(n)} $, per ogni $ n \in \mathbb{N}_0 $.
Resta da mostrare che $ g(n) \le 2n $: se $ \omega(n)=1 $ allora la tesi è vera in quanto (oltre i casi banali) $ g(p^\alpha) \le p^{\alpha-1}(p+1)< 2p^{\alpha} $ per ogni $ p \in \mathbb{P} $ e $ \alpha \in \mathbb{N}_0 $. Qui $ \omega(\cdot) $ è la funzione che conta il numero di divisori primi (cf.
qui ---
mod's edit).
Se $ \omega(n)=2 $ allora wlog $ n: =p_1^{\alpha_1}p_2^{\alpha_2}, 2 \le p_1<p_2 $ e $ \displaystyle g(n) \le \frac{n}{p_1p_2}(p_1+1)(p_2+1) \le 2n \implies p_2 \ge 1+\frac{2}{p_1-1} $. Ma tale disuguaglianza è sempre verificata infatti LHS vale al minimo 3 per ipotesi mentre RHS vale al massimo 3, e l'uguaglianza è quindi verificata
solo se $ p_1=2, p_2=3 $ (effettivamente l'uguaglianza è valida in quanto sono entrambi residui non quadratici modulo 5).
Possiamo vedere che se $ 5 \nmid n $ allora $ g(n) \le 2n \implies g(n \cdot 5^{\alpha}) =\mbox{lcm}\big(g(n),5^{\alpha}\big) \le 2n \cdot 5^{\alpha} $, per ogni $ \alpha \in \mathbb{N}_0 $.
Posto $ k := \omega(n) $, assumiamo quindi senza perdità che, se $ k \ge 2 $, la disuguaglianza $ g(n) \le 2n $ è sempre verificata e inoltre esiste sempre un primo dispari $ p_i \mid n $ diverso da 5. Dato che possiamo sempre assumere che $ p_1<p_2<p_3<\ldots $ allora aggiungere un fattore primo $ p_{k+1} $(maggiore di tutti gli altri) a $ n $ significherebbe verificare $ g(n\cdot p_{k+1}^{\alpha})=\mbox{lcm}\big(g(n),g(p_{k+1}^{\alpha})\big) \le $$ g(n) \cdot \frac{1}{2}p_{k+1}^{\alpha-1}(p_{k+1}+1) < 2n \cdot p_{k+1}^{\alpha} $, il che è vero, anzi, come disuguaglianza stretta.
Troviamo tutti gli $ n \in \mathbb{N}_0 $ tali che $ g(n)=2n $. In realtà è già tutto fatto: per quanto detto prima deve essere $ 2 \le \omega(n) \le 3 $. Adesso basta vedere che se $ \max\{\upsilon_2(n),\upsilon_3(n)\}>1 $ allora $ \gcd\big(g(2^{\upsilon_2(n)}), g(3^{\upsilon_3(n)})}\big)>1 $, per cui l'uguaglianza non sarebbe verificata. Inoltre se avesse tre fattori distinti diversi da 5 allora $ g(n)<2n $. Abbiamo concluso che tutti e soli i numeri che verificano $ g(n)=2n $ sono dati dalla classe $ 2 \cdot 3 \cdot 5^{\alpha}, \alpha \in \mathbb{N} $.
)!
