una successione fibonacciosa con p|x_p-1

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

una successione fibonacciosa con p|x_p-1

Messaggio da jordan » 09 dic 2009, 03:36

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.

Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll » 09 dic 2009, 14:38

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
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)

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

Messaggio da jordan » 09 dic 2009, 15:57

Wow Elì che piacere risentirti :o
The only goal of science is the honor of the human spirit.

Rispondi