Divisibilità e numeri di Fibonacci

[HiTLeuLeR]

Dimostrare che, per ogni $ n\in\mathbb{N}^+ $, esiste un intero positivo $ k \le 2n $ tale che $ n \mid f_{k} $, dove $ \{f_i\}_{i \ge 0} $ è la successione dei numeri di Fibonacci, definita assumendo $ f_0 = 0 $, $ f_1 = 1 $ ed $ f_{i+2} = f_{i+1} + f_i $, per ogni i = 0, 1, ... Provare inoltre che, in generale, il bound non può essere migliorato.

EDIT: senza grandi sforzi, sono riuscito ad abbassare il bound da 60n a 2n. Pertanto non vi sia meraviglia se il problema si presenta adesso in questa nuova versione.

[jordan]

Daqui.
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} $.

[karlosson_sul_tetto]

Dimostrare che, per ogni n\in\mathbb{N}^+, esiste un intero positivo k \le 2n tale che n \mid f_{k}, dove \{f_i\}_{i \ge 0} è la successione dei numeri di Fibonacci, definita assumendo f_0 = 0, f_1 = 1 ed f_{i+2} = f_{i+1} + f_i, per ogni i = 0, 1, ... Provare inoltre che, in generale, il bound non può essere migliorato.

EDIT: senza grandi sforzi, sono riuscito ad abbassare il bound da 60n a 2n. Pertanto non vi sia meraviglia se il problema si presenta adesso in questa nuova versione.

LOL
Non sapevo che davano compiti cosi difficili all'asilo!

[jordan]

$ n $-esimo post inutile (che non ho manco capito poi )!

[karlosson_sul_tetto]

In"che classe fai?"di birreria HiTLeuLeR aveva scritto:asilo.Ecco perche!

[jordan]

Ah, ok. La prossima volta mettici un link se la discussione non è proprio recente

[karlosson_sul_tetto]

Scusa,solo che mi sono scocciato e voglio dormiiiiireeeeeeeeee

[jordan]

Scusa,solo che mi sono scocciato e voglio dormiiiiireeeeeeeeee

1-Non devi scusarti
2-Scocciato di che?
3-Ok, allora buonanotte
4-L'hai letta almeno la dimostrazione?

[karlosson_sul_tetto]

No,dopo i primi due righi non capisco più niente!
Scocciato di fare il link

[jordan]

No,dopo i primi due righi non capisco più niente!

Non capisco allora perchè continui a rispondere

Scocciato di fare il link

A me non risulta che tu l'abbia mai fatto, almeno nella sezione olimpica

[Eulero]

bella dimostrazione!!!complimenti Jordan

[Giuseppe R]

Scusa,solo che mi sono scocciato e voglio dormiiiiireeeeeeeeee

Ciao, mi dispiace dirtelo (e so che non ho proprio diritto a farlo) ma non é una chat il forum, quindi se proprio devi rispondere, cerca almeno di parlare del problema, soprattutto in sezioni come queste, poi per chiarimenti (come ben sai) esiste la sezione fatta apposta e per osservazioni spiritose esiste la birreria.

[karlosson_sul_tetto]

ma non é una chat il forum

Avevo solo risposto a jordan:

La prossima volta mettici un link se la discussione non è proprio recente

[jordan]

Karlosson, se continui cosi propongo davvero di bannare te, almeno dalla sezione olimpica, (altro che Pikachù! )
Il gioco è bello quando dura poco.