$p$ divide $f_{p-1}$ oppure $f_{p+1}$

Numeri interi, razionali, divisibilità, equazioni diofantee, ...
Rispondi
Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

$p$ divide $f_{p-1}$ oppure $f_{p+1}$

Messaggio da jordan » 16 gen 2017, 22:50

Sia $p$ un primo fissato maggiore di $5$, e sia $(f_n)_{n\ge 1}$ la successione di Fibonacci definita da $f_1=f_2=1$ e $f_{n+2}=f_{n+1}+f_n$ per ogni $n\ge 1$.

Mostrare che $p$ divide esattamente uno tra $f_{p-1}$ e $f_{p+1}$.
The only goal of science is the honor of the human spirit.

Avatar utente
Gerald Lambeau
Messaggi: 335
Iscritto il: 17 mag 2015, 13:32
Località: provincia di Lucca

Re: $p$ divide $f_{p-1}$ oppure $f_{p+1}$

Messaggio da Gerald Lambeau » 17 gen 2017, 18:06

Intanto mostriamo che non può dividere entrambi.
Se $p \mid f_{p-1} \land p \mid f_{p+1}$ allora $p \mid f_p$, ma allora $p$ divide due elementi consecutivi della successione e, usando la definizione dei numeri di Fibonacci e un'induzione avanti e indietro, dividerebbe ogni numero della successione, anche $f_1=f_2=1$, assurdo! Questo varrebbe anche se dividesse due generici elementi consecutivi o distanti due posizioni, come in questo caso.

Ora, notiamo che essendo $p \not=5$ si ha $5^{p-1} \equiv 1 \pmod{p}$, ma vale anche che $p>5$, quindi $p-1$ è pari e $5^{p-1}$ è un quadrato, dunque $5^{p-1}-1=(5^{\frac{p-1}{2}}+1)(5^{\frac{p-1}{2}}-1) \equiv 0 \pmod{p}$, ma allora $5^{\frac{p-1}{2}} \equiv 1 \lor -1 \pmod{p}$.

Usiamo ora la formula di $f_n$ per calcolarci $f_{p+1}$.
$\displaystyle f_{p+1}=\frac{1}{\sqrt{5}}\left(\left(\frac{1+\sqrt{5}}{2}\right)^{p+1}-\left(\frac{1-\sqrt{5}}{2}\right)^{p+1}\right)$
$\displaystyle \frac{1}{\sqrt{5}}\left(\frac{\sum_{i=0}^{p+1} \sqrt{5}^i \binom{p+1}{i}}{2^{p+1}}-\frac{\sum_{i=0}^{p+1} (-\sqrt{5})^i \binom{p+1}{i}}{2^{p+1}}\right)$.
Ora portiamo tutto a denominator comune e notiamo, guardando i segni, come rimangano solo i termini con indice dispari nelle somme (si sommano, quindi moltiplicati per due), quindi ricordando che $p$ è dispari si ha
$\displaystyle \frac{1}{\sqrt{5}} \cdot \frac{2 \cdot \sum_{i=0}^{\frac{p-1}{2}} \sqrt{5}^{2i+1} \binom{p+1}{2i+1}}{2^{p+1}}$.
Semplificando otteniamo
$\displaystyle \frac{\sum_{i=0}^{\frac{p-1}{2}} 5^i \binom{p+1}{2i+1}}{2^p}$. Notiamo che questo numero è certamente intero e, dato che $p$ è dispari, dividere per una potenza di $2$ non cambia la divisibilità per $p$, quindi ci interessa solo a cosa è congruo il denominatore, e togliendo tutti i valori di $i$ per cui il binomiale risulta multiplo di $p$ ci rimane da controllare la congruenza di $\displaystyle 5^0 \binom{p+1}{1}+5^{\frac{p-1}{2}} \binom {p+1}{p}$,
cioè $p+1+5^{\frac{p-1}{2}}(p+1) \equiv 1+5^{\frac{p-1}{2}} \pmod{p}$.

Se $5^{\frac{p-1}{2}} \equiv -1 \pmod{p}$ allora $f_p \equiv 0 \pmod{p}$. Altrimenti, ricordando che dividevamo per $2^p$ otteniamo $f_p \equiv 2 \cdot 2^{-p}=2 \cdot (2^{-1})^p \equiv 2 \cdot 2^{-1}=1 \pmod{p}$. Ci basta quindi mostrare che in questo caso $f_p \equiv 1 \pmod{p}$ per avere che ad essere divisibile per $p$ è $f_{p-1}$ (questo segue da $f_{p+1}=f_p+f_{p-1}$.

Con passaggi analoghi a quelli fatti per $f_{p+1}$ e che quindi vi risparmio otteniamo che
$\displaystyle f_p=\frac{\sum_{i=0}^{\frac{p-1}{2}} 5^i \binom{p}{2i+1}}{2^{p-1}} \equiv \sum_{i=0}^{\frac{p-1}{2}} 5^i \binom{p}{2i+1} \pmod{p}$.
Ancora una volta togliamo gli elementi della somma multipli di $p$ a causa del binomiale, quindi resta
$\displaystyle f_p \equiv 5^{\frac{p-1}{2}} \binom{p}{p} \equiv 5^{\frac{p-1}{2}} \pmod{p}$. In questo caso abbiamo detto che vale $1$, quindi valgono le cose dette sopra e la tesi è dimostrata.



Scritta un po' di fretta, non riletta, è probabile, anzi è certa la presenza di typo.
"If only I could be so grossly incandescent!"

Avatar utente
jordan
Messaggi: 3988
Iscritto il: 02 feb 2007, 21:19
Località: Pescara
Contatta:

Re: $p$ divide $f_{p-1}$ oppure $f_{p+1}$

Messaggio da jordan » 17 gen 2017, 18:59

C'è qualche typo (tipo si guarda il numeratore e $f_{p+1}\equiv 0 \pmod{p}$) ma l'idea è chiara e mi pare corretta, anzi mostri piu' di quanto chiesto visto che trovi esattamente il resto di $f_{p+1}$. Copio qui sotto la mia soluzione:

Fix a prime $p\ge 7$. We have by Cassini's identity that
$$
F_{p-1}F_{p+1} = F_p^2-(-1)^{p-1} \,\,\,\,(=\, F_p^2-1).
$$
Hence, it is enough to prove that
$$
F_p^2 \equiv 1\pmod{p}.
$$
But we have
\begin{align*}
F_p^2&=\left(\frac{1}{\sqrt{5}}\left(\frac{1+\sqrt{5}}{2}\right)^p-\frac{1}{\sqrt{5}}\left(\frac{1-\sqrt{5}}{2}\right)^p\right)^2 \\\
&=\frac{1}{5}\left(\frac{1+\sqrt{5}}{2}\right)^{2p}+\frac{1}{5}\left(\frac{1-\sqrt{5}}{2}\right)^{2p}-\frac{2}{5}(-1)^p \\\
&=\frac{1}{5\cdot 2^{2p}}\left(1+\sqrt{5}\right)^{2p}+\frac{1}{5\cdot 2^{2p}}\left(1-\sqrt{5}\right)^{2p}+\frac{2}{5} \\\
&=\frac{1}{5\cdot 2^{p}}\left(3+\sqrt{5}\right)^{p}+\frac{1}{5\cdot 2^{2p}}\left(3-\sqrt{5}\right)^{2p}+\frac{2}{5} \\\
&=\frac{1}{5\cdot 2^{p}}\left(2\sum_{i=0, i\text{ even}}^p\binom{p}{i}3^{p-i}\sqrt{5}^i\right)+\frac{2}{5} \\\
&=\frac{1}{5\cdot 2^{p-1}}\left(\sum_{j=0}^{\frac{p-1}{2}}\binom{p}{2j}3^{p-2j}5^j\right)+\frac{2}{5}.
\end{align*}

At this point, considering that $p\mid \binom{p}{j}$ for $0<j<p$, we conclude that
$$
F_p^2 \equiv \frac{3^p}{5\cdot 2^{p-1}}+\frac{2}{5}\equiv \frac{3}{5}+\frac{2}{5}\equiv 1\pmod{p}.
$$
The only goal of science is the honor of the human spirit.

ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: $p$ divide $f_{p-1}$ oppure $f_{p+1}$

Messaggio da ma_go » 29 gen 2017, 23:32

qualcuno mi propone una soluzione che evita i conti?

Rispondi