OliForum Matematico

Consideriamo la sequenza di Fibonacci $f_0=0$, $f_1=1$, $f_n=f_{n-1}+f_{n-2}$ modulo $p^k$.
1. Dimostrare che tale sequenza modulo $p^k$ è periodica e non ha antiperiodo. Sia $\pi(p^k)$ la lunghezza del periodo.
2. Dimostrare che per ogni primo $p\equiv \pm1\ \bmod 5$ si ha $\pi(p)\vert p-1$.
3. Dimostrare che per ogni primo $p\equiv \pm2\ \bmod 5$ si ha $\pi(p)\vert 2(p+1)$.
4. Dimostrare che per ogni primo $p$ si ha $\pi(p^k)\leq p^{k-1}\pi(p)$, con uguaglianza se $\pi(p)\neq \pi(p^2)$.

Es: modulo $3$ la sequenza di Fibonacci è
$$0,\ 1,\ 1,\ 2,\ 0,\ 2,\ 2,\ 1,\ 0,\ 1,\ 1,\ 2,\ 0,\ 2,\ 2,\ 1,\ 0,\ 1,\ldots$$
quindi $\pi(3)=8=2(3+1)$. Inoltre, modulo $9$ si ha
$$0,\ 1,\ 1,\ 2,\ 3,\ 5,\ 8,\ 4,\ 3,\ 7,\ 1,\ 8,\ 0,\ 8,\ 8,\ 7,\ 6,\ 4,\ 1,\ 5,\ 6,\ 2,\ 8,\ 1,\ 0,\ 1,\ldots$$
e dunque $\pi(9)=24$; poiché $\pi(3)\neq\pi(9)$ vale $\pi(3^k)=8\cdot 3^{k-1}$ (e vale anche per $k=2$).

Mi hai fregato il thread... volevo aprirne uno praticamente uguale Ma il mio sarebbe stato più ganzo perchè c'avrei messo anche:
Dimostrare che per ogni primo $p$ vale $F_p^3\equiv F_p\pmod{p}$

Beh, io non metto richieste inutili XD. Però se fossi stato buono (e non lo sono) avrei potuto ricordare a tutti che $(A+B)^p\equiv A^p+B^p\ \bmod p$ ...

Risolvo per ora 1 e 2, perché devo scappare . Considero per ogni $h\geq 0$ la coppia $(f_h,f_{h+1})$ modulo $p^k$. Di queste coppie ce ne possono essere al massimo $p^{2k}$. Ora considero i primi $p^{2k}+2$ numeri di fibonacci modulo $p^k$. Prendendoli a coppie come ho indicato all'inizio ho $p^{2k}+1$ coppie, quindi per pigeonhole ce ne saranno due uguali. E allora sicuramente la sequenza è periodica perché se una coppia si ripete, si ripete pari pari tutto ciò che sta dopo, essendo determinato dai due precedenti.
Suppongo ora ci sia un antiperiodo $\overline{a_0a_1...a_n}$ e un periodo $\overline{b_0b_1...b_k}$. Ora due elementi della serie determinano anche il precedente ed essendo $b_k+b_0=b_1$ si deve avere anche $b_k=a_n$, $b_{k-1}=a_{n-1}$ e così via. Se $n \geq k$, allora in questa maniera riesco a trovare un altro periodo nell'antiperiodo, assurdo. Se invece $n<k$, allora $a_{0}=b_{k-n}$ e $a_{1}=b_{n-k+1}$, perciò la sequenza è periodica fin dall'inizio. (Tutto ciò vale anche modulo un generico $n$).

2. Mi basta mostrare che $p|F_{p-1}$ e $p|F_p-1$.
Innanzitutto, so che $F_n= \dfrac{1}{\sqrt {5}}(\phi^n-(1-\phi)^n)$. Con un po' di calcoli, semplificando il semplificabile si ottiene $F_n = \dfrac{1}{2^{n-1}}\displaystyle\sum_{i=0}^{\lfloor\frac{n-1}{2} \rfloor} \binom{n}{2i+1} 5^i$.
Allora si ha $F_p = \dfrac{1}{2^{p-1}}\displaystyle\sum_{i=0}^{\frac{p-1}{2}} \binom{p}{2i+1} 5^i$. Analizzando tutto modulo $p$ i binomiali vanno tutti via tranne l'ultimo, perché tutti gli altri hanno esattamente un $p$ al numeratore ed esattamente $0$ al denominatore. Allora $F_p \equiv 5^{\frac{p-1}{2}} \equiv 1 \pmod p$, perché per la reciprocità quadratica in questo caso $5$ è residuo quadratico.
Ora si ha che $F_{p-1} = \dfrac{1}{2^{p-2}}\displaystyle\sum_{i=0}^{\frac{p-3}{2}} \dfrac{(p-1)!}{(2i+1)!(p-2i-2)!} 5^i$.
Ma si ha che $(-1)^{2i+1} (2i+1)! (p-2i-2) \equiv (p-1)! \pmod p$. Essendo tutto allegramente invertibile, allora si ha $F_{p-1} \equiv \dfrac{1}{2^{p-2}} \displaystyle\sum_{i=0}^{\frac{p-3}{2}} (-1)^{2i+1}5^i \equiv -\dfrac{1}{2^{p-2}} \dfrac{5^{\frac{p-1}{2}}-1}{4} \equiv 0 \pmod p$ sempre perché $5^{\frac{p-1}{2}} \equiv 1 \pmod p$ essendo residuo quadratico.

A breve il punto 3)

Ok! Per il punto 1. puoi più semplicemente osservare che ad un certo punto deve ripetersi per il principio dei cassetti (come hai fatto) e poi notare che l'algoritmo è reversibile ($a_{n-2}=a_n-a_{n-1}$); periodico+reversibile ==> puramente periodico.

Metto due soluzioni al punto 3, una più bella e una più contosa (stavo scrivendo quella contosa e mi è venuta quella bella)

Innanzitutto verifico la tesi per $p=2$, così posso supporre $p$ dispari. Per $p=2$ si ha $\pi(2)=3|6$ e quindi ok.
Ora vale ancora $F_p \equiv 5^{\frac{p-1}{2}} \pmod p$ perché per dimostrarlo utilizzo solo l'invertibilità di $2$ modulo $p$, che è garantita. Analogamente vale sempre $F_{p-1} \equiv -\dfrac{1}{2^{p-2}}\dfrac{5^{\frac{p-1}{2}}-1}{4} \pmod p$. Ora se $p \equiv \pm 2 \pmod 5$, allora $5$ non è residuo quadratico. Dunque $F_p \equiv -1 \pmod p$ e $F_{p-1} \equiv \dfrac{1}{2^{p-1}} \equiv 1 \pmod p$. Dunque $F_{p+1} \equiv 0 \pmod p$ e $F_{p+2} \equiv -1 \pmod p$. In particolare la sequenza di fibonacci è ricominciata, ma col segno opposto. Sicuramente allora $F_{2p+2} \equiv 0 \pmod p$ e $F_{2p+3} \equiv -F_{p+2} \equiv 1 \pmod p$ e quindi il periodo è un sottomultiplo di $2p+2$.

Per la soluzione contosa mi levo subito dalle scatole $p=2$ e $p=3$ che soddisfano.
Mi basta mostrare che $p|F_{2p+2}$ e $p|F_{2p+3}-1$.
Per quanto scritto prima si ha che $F_{2p+2} = \dfrac{1}{2^{2p+1}}\displaystyle\sum_{i=0}^{p} \binom{2p+2}{2i+1}5^i$. Ora, si ha che per ogni $i$ tranne $i=0,\dfrac{p-1}{2},\dfrac{p+1}{2},p$, $p|\displaystyle\binom{2p+2}{2i+1}$ perché in quasto caso al numeratore ci sono esattamente due fattori $p$ e al denominatore esattamente uno. Quindi, vedendo tutto modulo $p$ si ha
$$F_{2p+2} \equiv \dfrac{1}{2^{2p+1}}\left(\displaystyle\binom{2p+2}{1}+\displaystyle\binom{2p+2}{p}5^{\frac{p-1}{2}}+\displaystyle\binom{2p+2}{p+2}5^{\frac{p+1}{2}}+\displaystyle\binom{2p+2}{2p+1}5^p\right) \pmod p$$
Poi
$$\binom{2p+2}{p} = \binom{2p+2}{p+2} = \dfrac{(2p+2)!}{p!(p+2)!} = \dfrac{(p-1)!(p+1)\dots(p+(p-1))\cdot 2(2p+1)(2p+2)}{(p-1)!(p-1)!(p+1)(p+2)} \equiv$$
$$\equiv \dfrac{(p-1)!(p-1)!\cdot 4}{(p-1)!(p-1)!\cdot 2} \equiv 2 \pmod p$$

Per questo e per il fatto che $5^{\frac{p-1}{2}} \equiv -1 \pmod p$, non essendo $5$ un residuo quadratico, si ha che $F_{2p+2} \equiv \dfrac{1}{2^{2p+1}}(2+2\cdot(-1)+2\cdot(-5)+2\cdot5) \equiv 0 \pmod p$.

Per l'altra congruenza, si ha $F_{2p+3} = \dfrac{1}{2^{2p+2}}\displaystyle\sum_{i=0}^{p+1} \displaystyle\binom{2p+3}{2i+1}5^i$. Ora come prima per ogni $i$ tranne che per $i=0,1,\dfrac{p-1}{2},\dfrac{p+1}{2},p,p+1$ si ha $p|\displaystyle\binom{2p+3}{2i+1}$. Quindi rimane da mostrare che
$$\dfrac{1}{2^{2p+2}}\left(\displaystyle\binom{2p+3}{1}+\displaystyle\binom{2p+3}{3}\cdot 5 + \displaystyle\binom{2p+3}{p}5^{\frac{p-1}{2}} + \displaystyle\binom{2p+3}{p+2}5^{\frac{p+1}{2}} + \displaystyle\binom{2p+3}{2p+1}5^p + \displaystyle\binom{2p+3}{2p+3}5^{p+1}\right) \equiv 1 \pmod p$$

Si ha che
$$\binom{2p+3}{p} = \dfrac{(2p+3)!}{p!(p+3)!} = \dfrac{(p-1)!(p+1)\dots(p+(p-1))\cdot 2(2p+1)(2p+2)(2p+3)}{(p-1)!^2(p+1)(p+2)(p+3)} \equiv 2 \pmod p$$

Similmente $\displaystyle\binom{2p+3}{p+2} \equiv 6 \pmod p$. Allora la parentesi di prima fa $\dfrac{3+1\cdot 5 +2\cdot (-1) + 6\cdot (-5) + 3\cdot 5 +1\cdot 25}{2^{2p+2}} \equiv \dfrac{16}{\left(2^{p+1}\right)^2} \equiv 1 \pmod p$. [Quest'ultimo ragionamento vale se $p>5$, ecco perché mi sono tolto subito dalle scatole $2$ e $3$).

Boh, accontento dario2994. Avendo $F_p \equiv 5^{\frac{p-1}{2}} \pmod p$, se $p \neq 2$, Allora $F_p^2 \equiv 5^{p-1} \equiv 1 \pmod p$. Quindi sicuramente $F_p^3 \equiv F_p \pmod p$, poiché $p|F_p^2-1|F_p^3-F_p$. $p=2$ si verifica a mano.

Ora passo al punto 4. Utilizzerò una formula che è stata provata su questo forum (grazie a kn !): $\displaystyle\sum_{k=0}^n \binom{n}{k}F_t^kF_{t-1}^{n-k}F_{m+k} =F_{nt+m}$, dimostrata in questo thread. Bene, voglio mostrare che per ogni $k$ si ha che $\pi(p^{k+1}) \leq p\pi(p^{k})$. E' chiaro che $\pi(p^k)|\pi(p^{k+1})$, per dimostrare la disuguaglianza mi basta mostrare che $F_{p\cdot\pi(p^{k})} \equiv 0 \pmod{p^{k+1}}$ e $F_{p\cdot\pi(p^{k})+1} \equiv 1 \pmod{p^{k+1}}$. Chiamo per semplicità $\pi(p^k)=x$. So che $p^{k}|F_x$ e $p^k|F_{x+1}-1$. Ora uso la formula e ottengo
$$
F_{px} = \sum_{i=0}^p \binom{p}{i}F_iF_x^iF_{x-1}^{p-i} \equiv \binom{p}{0}F_0F_x^0F_{x-1}^p + \binom{p}{1}F_1F_x^1F_{x-1}^{p-1} \equiv pF_xF_{x-1}^{p-1} \equiv 0 \pmod{p^{k+1}}$$
$$
F_{px+1} = \sum_{i=0}^p \binom{p}{i}F_{i+1}F_x^iF_{x-1}^{p-i} \equiv \binom{p}{0}F_1F_x^0F_{x-1}^p + \binom{p}{1}F_2F_x^1F_{x-1}^{p-1} \equiv F_{x-1}^p \pmod{p^{k+1}}
$$
Ma si ha che $F_{x-1} \equiv F_{x+1}-F_x \equiv 1 \pmod{p^k}$. Dunque per qualche $j$, $F_{x-1} = jp^k+1$. Ma allora $(jp^k+1)^p = \displaystyle\sum_{i=0}^p \binom{p}{i}(jp)^{ik}\equiv 1 \pmod{p^{k+1}}$. Dunque si ha $\pi(p^{k+1})|p\pi(p^k)$ e quindi $\pi(p^{k+1}) \leq p\pi(p^k)$ e applicando sempre la stessa proprietà, per induzione, $\pi(p^{k+1}) \leq p^k\pi(p)$.

Per quanto concluso fino ad ora, e per quello detto all'inizio ($\pi(p^k)|\pi(p^{k+1})$), posso concludere che $\pi(p^k)|\pi(p^{k+1})|p\pi(p^k)$. Quindi si possono avere due possibilità: $\pi(p^{k+1})=\pi(p^k)$ oppure $\pi(p^{k+1}) = p\pi(p^k)$. Se $\pi(p) \neq \pi(p^2)$ allora sicuramente $\pi(p)=p\pi(p)$. Ora sia $k$ il più piccolo naturale tale che $\pi(p^{k+2})=\pi(p^{k+1})$. Allora guardando le precedenti due $F_{px}$ e $F_{px+1}$ modulo $p^{k+2}$, devono ancora valere. Sicuramente $p\nmid F_{x-1}$, dunque affinché $p^{k+2}|F_{px}$, si deve avere $p^{k+1}|F_x$. Analogamente affinché $p^{k+2}|F_{px+1}-1$ si deve avere $F_{px+1}\equiv F_{x-1}^p \equiv jp^{k+1}+1 \equiv 1 \pmod{p^{k+2}}$, da cui $j \equiv 0 \pmod p$ e quindi $F_{x-1} \equiv 1 \pmod{p^{k+1}}$. Per l'assunzione di minimo si deve avere $\pi(p^{k+2})=\pi(p^{k+1})=p\pi(p^k)$. Ma per quello che ho appena mostrato $\pi(p^{k+1})|\pi(p^k)$, assurdo.

Quindi se $\pi(p) \neq \pi(p^2)$ allora $\pi(p^k)=p^{k-1}\pi(p)$.

Vista la dimostrazione di sopra del 4., in generale si può scrivere che se $x$ è il più piccolo indice tale che $p|F_x$ e $p|F_{x+1}-1$, allora sia $a=min(v_p(F_x),v_p(F_{x+1}-1))$: si ha che $\pi(p^a)=\pi(p)$ e $\pi(p^{a+1})\neq \pi(p^a)$, ovvero $\pi(p^{a+1})=p\pi(p)$ e in generale, poiché a partire da ora non ci possono essere più uguaglianze (vedi dimostrazione precedente), $\pi(p^{a+k})=p^k\pi(p)$.

Aggiungo un altro bonus, che non ho ancora mostrato. Sia $x$ il più piccolo indice tale che $n$, con $n$ naturale generico, divide $F_x$, allora $\pi(n) \in \{x,2x,4x\}$.

Tu risolvi il mio bonus.... e io risolvo il tuo
$F_{x-1}\equiv F_{x+1}-F_x\equiv F_{x+1}\pmod{n}$
Quindi vale: $(-1)^x\equiv F_{x-1}F_{x+1}-F_x^2\equiv F_{x+1}^2 \pmod n\Rightarrow Ord_n(F_{x+1})|4$
Bon... da qui basta notare che $\pi(n)=Ord_n(F_{x+1})\cdot x$ e viene la tesi.

Dato che non mi va di dimostrarlo lo piazzo come ennesimo bonus, ma è facile facile :
Bonus della locomotiva: Con le notazioni di sopra, dimostrate che $\pi(n)=Ord_n(F_{x+1})\cdot x$

Risolvo il bonus di belcolon (non aspettarti gli accenti nel tuo nick) così vi mostro come si può lavorare con le matrici per trattare i numeri di fibonacci.
Chiamo $F=\begin{pmatrix}0 & 1\\1 &12\end{pmatrix}$.
Allora $F\begin{pmatrix}x\\y\end{pmatrix}=\begin{pmatrix}y\\x+y\end{pmatrix}$.
In particolare $F^k\begin{pmatrix}0\\1\end{pmatrix}=\begin{pmatrix}F_k\\F_{k+1}\end{pmatrix}$. O, in altro modo
$$F^k=\begin{pmatrix}F_{k-1} & F_k\\F_k & F_{k+1}\end{pmatrix}$$
$\pi(n)$ è dunque il più piccolo intero positivo $m$ tale che $F^m\equiv I \ \bmod n$, dove $I$ è la matrice identità ($1$ sulla diagonale, $0$ fuori).
Sia invece $x(n)$ il più piccolo intero positivo $x$ tale che $n\mid F_x$, allora $F^x\equiv a I\ \bmod n$. Infatti, se $F_x\equiv 0 \ \bmod n$, allora $F_{x+1}\equiv F_{x-1}\equiv a \ \bmod n$. D'altra parte,
$$F_{x}^2-F_{x-1}F_{x+1}=-\det F^x=-(\det F)^x=(-1)^{x+1}$$
dunque $a^2\equiv (-1)^x$, dunque $a$ può avere ordine $1$, $2$ o $4$.
Se $a$ ha ordine $1$, allora $x(n)=\pi(n)$; se $a$ ha ordine maggiore di $1$, da $F_x$ parte modulo $n$ una successione di Fibonacci moltiplicata per $a$, ovvero $F_{x+k}=aF_k$; quindi $F_{2x+1}=a^2$ e $F_{4x+1}=a^4$. Uno di questi è $1$, quindi il periodo è $x(n)$, $2x(n)$ o $4x(n)$ a seconda che $F_{x+1}$ abbia ordine $1$, $2$ o $4$ modulo $n$.

Beh, a questo punto.... ultimo passo.
Dato $m=p_1^{a_1}\cdot\ldots\cdot p_k^{a_k}$, quanto vale $\pi(m)$?