una successione fibonacciosa con p|x_p-1
una successione fibonacciosa con p|x_p-1
Definiamo la successione degli $ \{x_i\}_{i \in \mathbb{N}_0} \subseteq \mathbb{Z} $ tale che $ x_2=x_1+2=3 $ e $ x_{n+2}=x_n+x_{n+1} $ per ogni $ n \in \mathbb{N}_0 $. Mostrare che $ p \mid x_p-1 $ per ogni $ p \in \mathbb{P} $.
The only goal of science is the honor of the human spirit.
Aggiungiamo un elemento ausiliario $ x_0=2 $, poi sfruttando il fatto che la soluzione sia combinazione lineare delle due radici di $ x^2-x-1 $ ricaviamo la formula generale.
$ $ x_n=\frac{(1+\sqrt{5})^n+(1-\sqrt{5})^n}{2^n} $
La cosa da dimostrare diventa quindi:
$ (1+\sqrt{5})^p+(1-\sqrt{5})^p \equiv 2^p \bmod p $
ovvero, sfruttando il piccolo teorema di Fermat
$ $ \sum_{i=0}^{p}\binom{p}{i}((\sqrt{5})^i+(-\sqrt{5})^i)\equiv 2 $
Considerando che solo per i=0 e i=p il binomiale non è multiplo di p avremo che la nostra espressione diventa:
$ $ \binom{p}{0}(1+1)+\binom{p}{p}(0)\equiv 2 $
quindi
$ 2\equiv 2 $
qed
$ $ x_n=\frac{(1+\sqrt{5})^n+(1-\sqrt{5})^n}{2^n} $
La cosa da dimostrare diventa quindi:
$ (1+\sqrt{5})^p+(1-\sqrt{5})^p \equiv 2^p \bmod p $
ovvero, sfruttando il piccolo teorema di Fermat
$ $ \sum_{i=0}^{p}\binom{p}{i}((\sqrt{5})^i+(-\sqrt{5})^i)\equiv 2 $
Considerando che solo per i=0 e i=p il binomiale non è multiplo di p avremo che la nostra espressione diventa:
$ $ \binom{p}{0}(1+1)+\binom{p}{p}(0)\equiv 2 $
quindi
$ 2\equiv 2 $
qed
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
