Fibonacci, what else?

Tolaso J Kos · #1

Έστω

ο

- οστός αριθμός Fibonacci. Να δειχθεί ότι:

$\displaystyle{\gcd \left(f_m,f_n \right)=f_{\gcd(m, n)}}$
όπου $m, n \geq 1$ .

bouzoukman · #2

Θα αποδείξω το μισό και το άλλο θα το προσπαθήσω αύριο. Έστω $\alpha=\frac{1+\sqrt{5}}{2}$ και $\beta=\frac{1-\sqrt{5}}{2}$ . Τότε είναι γνωστό ότι $f_n=\frac{\alpha^n-\beta^n}{\sqrt{5}}$ . Έστω $d=\gcd(n,m)$ , τότε έχουμε ότι n=n_1d

και

. Επομένως ισχύει ότι

$\displaystyle{ f_n=\frac{\alpha^n-\beta^n}{\sqrt{5}}=\frac{(\alpha^d)^{n_1}-(\beta^d)^{n_1}}{\sqrt{5}}=\frac{\alpha^d-\beta^d}{\sqrt{5}}\left(\alpha^{d(n_1-1)} + \alpha^{d(n_1-2)}\beta^d+\cdots + \beta^{d(n_1-1)})\right)=f_{\gcd(n,m)}\cdot A, }$

όπου $A = \alpha^{d(n_1-1)} + \alpha^{d(n_1-2)}\beta^d+\cdots + \beta^{d(n_1-1)}\in\mathbb{Z}$ . Οπότε έχουμε αποδείξει ότι $f_{\gcd(n,m)}\mid f_n$ , ομοίως έχουμε ότι $f_{\gcd(n,m)}\mid f_m$ . Επομένως, $f_{\gcd(n,m)}\mid \gcd(f_n,f_m)$ .

bouzoukman · #3

Χρόνια πολλά και καλή χρονιά κι από εμένα! Δυστυχώς δεν βρήκα κάποια απόδειξη για το άλλο μισό χρησιμοποιώντας μόνο στοιχειώδη θεωρία αριθμών! Όποιος έχει μία με χαρά θα ήθελα να την δω.

Με τον συμβολισμό όπως στο παραπάνω post έστω $w\mid(f_n, f_m)$ , τότε ισχύει $w\mid\frac{\alpha^n + \beta^n}{\sqrt{5}}$ και $w\mid\frac{\alpha^m-\beta^m}{\sqrt{5}}$ . Δουλεύοντας τώρα πάνω από το δακτύλιο των ακεραίων του $\mathbb{Q}(\sqrt{5})$ , που είναι ο $\mathbb{Z}[\frac{1+\sqrt{5}}{2}]$ , προκύπτει ότι

$\displaystyle{ \alpha^n\equiv\beta^n\pmod{w\sqrt{5}}, \qquad \alpha^m\equiv\beta^m\pmod{w\sqrt{5}}. }$

Εφόσον (n,m)=d

, ισχύει ότι $\lambda n + \mu m=d$ για κάποια $\lambda,\mu\in\mathbb{Z}$ . Από τις παραπάνω δύο σχέσεις καταλαβαίνουμε ότι ισχύει (κάποιος πρέπει να είναι προσεκτικός εδώ και να δείξει ότι τα $\alpha,\beta$ είναι πρώτα με το $w\sqrt{5}$ )

$\displaystyle{ \alpha^d\equiv\beta^d\pmod{w\sqrt{5}}\Rightarrow w\mid\frac{\alpha^d-\beta^d}{\sqrt{5}}=f_d. }$

Από την τελευταία σχέση βγαίνει το συμπέρασμα ότι $(f_n,f_m)\mid f_d$ . Εφόσον έχουμε αποδείξει, στο προηγούμενο post, ότι $f_d\mid (f_n,f_m)$ το ζητούμενο έπεται!

Απορία/Ερώτηση: Μιας και η ακολουθία Fibonacci ανήκει στην οικογέγεια των Lucas ακολουθιών, γεννιέται το ερώτημα αν η παραπάνω ιδιότητα ισχύει για όλες τις Lucas ακολουθίες;

#4

Ένας στοιχειώδης τρόπος για το άλλο μισό:

Θα χρησιμοποιήσουμε την ταυτότητα $\displaystyle F_n^2 + (-1)^{n-m}F_m^2 = F_{n-m}F_{n+m}$ . (Αποδεικνύεται εύκολα από τον τύπο που παρέθεσε ο Bouzouman. Ο τύπος ισχύει για οποιοδήποτε ακεραίους m,n

, όχι απαραίτητα φυσικούς.)

Από τον τύπο παρατηρούμε ότι $d|F_n,F_m \implies d|F_{n-m},F_{n-m}$ . Επαγωγικά βρίσκουμε και ότι $d|F_{am+bn}$ για οποιουσδήποτε ακέραιους a,b

. Άρα ισχύει και $d|F_{\mathrm{gcd}(m,n)}$ που είναι και το ζητούμενο.

bouzoukman · #5

Demetres έγραψε: ↑
Κυρ Ιαν 03, 2021 12:39 pm
Από τον τύπο παρατηρούμε ότι $d|F_n,F_m \implies d|F_{n-m},F_{n-m}$ .

Καλησπέρα σας! Δεν είμαι σίγουρος ότι από τον τύπο $\displaystyle F_n^2 + (-1)^{n-m}F_m^2 = F_{n-m}F_{n+m}$ μπορούμε να αποδείξουμε το παραπάνω. Αυτό που παίρνουμε είναι ότι $d^2\mid F_{n-m}F_{n+m}$ . Παρόλα αυτά, η ιδέα να επεκτείνουμε τον τύπο $F_n=\frac{\alpha^n - \beta^n}{\sqrt{5}}$ και για αρνητικές τιμές του

νομίζω ότι είναι αρκετό (και πάρα πολύ καλή ιδέα!).

#6

bouzoukman έγραψε: ↑
Κυρ Ιαν 03, 2021 10:26 pm

Demetres έγραψε: ↑
Κυρ Ιαν 03, 2021 12:39 pm
Από τον τύπο παρατηρούμε ότι $d|F_n,F_m \implies d|F_{n-m},F_{n-m}$ .
Καλησπέρα σας! Δεν είμαι σίγουρος ότι από τον τύπο $\displaystyle F_n^2 + (-1)^{n-m}F_m^2 = F_{n-m}F_{n+m}$ μπορούμε να αποδείξουμε το παραπάνω. Αυτό που παίρνουμε είναι ότι $d^2\mid F_{n-m}F_{n+m}$ .

Σαφώς και έχεις δίκαιο.

Fibonacci, what else?

Fibonacci, what else?

Re: Fibonacci, what else?

Re: Fibonacci, what else?

Re: Fibonacci, what else?

Re: Fibonacci, what else?

Re: Fibonacci, what else?

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