Διαιρετότητα με Fibonacci!

#1

Σε συνέχεια αυτού:

Ας είναι $\displaystyle{\rm p>5}$ πρώτος. Να αποδείξετε ότι

$\displaystyle{\boxed{\rm p|F_{p-1}\iff p\equiv 1,4~ mod 5}}$

$\displaystyle{\boxed{ \rm p|F_{p+1}\iff p\equiv 2,3~ mod 5}}$

#2

Για κάθε θετικό ακέραιο

ισχύει:

$\displaystyle{ F_n=\frac{1}{2^{n-1}}\sum_{r=0}^{\left[ \frac{n-1}{2} \right]}{\binom{n}{2r+1}5^r}. }$

Επειδή $\displaystyle{\binom{p}{r}\equiv 0\left( \mathrm{mod} p \right) }$ για 0<r<p

και $2^{p-1}\equiv 1\left( \mathrm{mod} p \right)$ (από το Μικρό Θεώρημα του Fermat), έχουμε ότι:

$\displaystyle{F_p\equiv 2^{p-1}F_p=\sum_{r=0}^{\frac{p-1}{2}}{\binom{p}{2r+1}5^r}\equiv 5^{\frac{p-1}{2}}\left( \mathrm{mod} p \right). }$

και

$\displaystyle{ 2F_{p+1}\equiv 2^pF_{p+1}=\sum_{r=0}^{\frac{p-1}{2}}{\left\{ \binom{p}{2r+1}+\binom{p}{2r} \right\} 5^r}\equiv 1+5^{\frac{p-1}{2}}\left( \mathrm{mod} p \right). }$

Άρα, είναι:

$\displaystyle{ 2F_{p-1}=2F_{p+1}-2F_p\equiv 1+5^{\frac{p-1}{2}}-2\cdot 5^{\frac{p-1}{2}}\left( \mathrm{mod} p \right) =1-5^{\frac{p-1}{2}}\left( \mathrm{mod} p \right). }$

Επομένως, είναι:

$\displaystyle{ p|F_{p-1}\Longleftrightarrow 5^{\frac{p-1}{2}}\equiv 1\left( \mathrm{mod} p \right) \Longleftrightarrow \left( \frac{5}{p} \right) =1\Longleftrightarrow p\equiv 1,4\left( \mathrm{mod} 5 \right) }$

και

$\displaystyle{ p|F_{p+1}\Longleftrightarrow 5^{\frac{p-1}{2}}\equiv -1\left( \mathrm{mod} p \right) \Longleftrightarrow \left( \frac{5}{p} \right) =-1\Longleftrightarrow p\equiv 2,3\left( \mathrm{mod} 5 \right). }$

Σημείωση: Γενικά, αν

περιττός πρώτος, τότε ο

διαιρεί ακριβώς έναν από τους αριθμούς $F_{p-1}$ , F_p

, $F_{p+1}$ και συγκεκριμένα τον F_m

, όπου $\displaystyle{m=p-\left( \frac{5}{p} \right). }$

Διαιρετότητα με Fibonacci!

Διαιρετότητα με Fibonacci!

Re: Διαιρετότητα με Fibonacci!

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