Fibonacci και διαιρετότητα

M.S.Vovos · #1

Έστω $F_{n}$ η ακολουθία Fibonacci. Να αποδείξετε ότι για κάθε πρώτο p>5

ισχύει $\displaystyle{p|F_{p-1}}$ ή $\displaystyle{p|F_{p+1}}$ .

Φιλικά.

#2

Από την ταυτότητα Cassini είναι αρκετό να αποδείξουμε ότι

$\displaystyle{F_p ^2 \equiv 1\mod p}$ .

Είναι

$\displaystyle{F_p=\frac{1}{\sqrt{5}2^p}[(1+\sqrt{5})^p-(1-\sqrt{5})^p]=\frac{1}{\sqrt{5}2^p}\sum_{k=0}^{p}\binom{p}{k}\sqrt{5}^k(1-(-1)^k)=}$

$\displaystyle{=\frac{1}{\sqrt{5}2^p}\sum_{k ~odd}\binom{p}{k}2\sqrt{5}^k}$

άρα

$\displaystyle{2^{p-1}F_p=\sum_{k~odd}\binom{p}{k}5^{\frac{k-1}{2}}}$ .

Παίρνοντας στη σχέση αυτή $\displaystyle{\mod p,}$ επειδή είναι $\displaystyle{\binom{p}{k}\equiv 0\mod p}$ όταν $\displaystyle{k<p}$ προκύπτει

$\displaystyle{2^{p-1}F_p\equiv 5^{\frac{p-1}{2}}\mod p,}$ οπότε με ύψωση στο τετράγωνο και με χρήση του θεωρήματος Fermat, βρίσκουμε $\displaystyle{F_p ^2\equiv 1\mod p,}$ δηλαδή το ζητούμενο.

Fibonacci και διαιρετότητα

Fibonacci και διαιρετότητα

Re: Fibonacci και διαιρετότητα

Μέλη σε σύνδεση