Fibonacci, what else?

Συντονιστής: nkatsipis

Άβαταρ μέλους
Tolaso J Kos
Δημοσιεύσεις: 4582
Εγγραφή: Κυρ Αύγ 05, 2012 10:09 pm
Τοποθεσία: Λάρισα, Βαρκελώνη
Επικοινωνία:

Fibonacci, what else?

#1

Μη αναγνωσμένη δημοσίευση από Tolaso J Kos » Παρ Δεκ 25, 2020 1:09 pm

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

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


Η φαντασία είναι σημαντικότερη από τη γνώση !
\displaystyle{{\color{blue}\mathbf{Life=\int_{birth}^{death}\frac{happiness}{time}\Delta time} }}

Λέξεις Κλειδιά:
bouzoukman
Δημοσιεύσεις: 115
Εγγραφή: Δευ Ιαν 19, 2009 7:53 pm
Επικοινωνία:

Re: Fibonacci, what else?

#2

Μη αναγνωσμένη δημοσίευση από bouzoukman » Τρί Δεκ 29, 2020 11:48 pm

Θα αποδείξω το μισό και το άλλο θα το προσπαθήσω αύριο. Έστω \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 και m=m_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).


"Υπάρχει αρκετό φως γι' αυτούς που επιθυμούν να δουν και αρκετό σκοτάδι γι' αυτούς που έχουν την αντίθετη επιθυμία", B. Pascal
bouzoukman
Δημοσιεύσεις: 115
Εγγραφή: Δευ Ιαν 19, 2009 7:53 pm
Επικοινωνία:

Re: Fibonacci, what else?

#3

Μη αναγνωσμένη δημοσίευση από bouzoukman » Κυρ Ιαν 03, 2021 11:37 am

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

Με τον συμβολισμό όπως στο παραπάνω 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 ακολουθίες;


"Υπάρχει αρκετό φως γι' αυτούς που επιθυμούν να δουν και αρκετό σκοτάδι γι' αυτούς που έχουν την αντίθετη επιθυμία", B. Pascal
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8615
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Fibonacci, what else?

#4

Μη αναγνωσμένη δημοσίευση από Demetres » Κυρ Ιαν 03, 2021 12:39 pm

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

Θα χρησιμοποιήσουμε την ταυτότητα \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
Δημοσιεύσεις: 115
Εγγραφή: Δευ Ιαν 19, 2009 7:53 pm
Επικοινωνία:

Re: Fibonacci, what else?

#5

Μη αναγνωσμένη δημοσίευση από 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}. Παρόλα αυτά, η ιδέα να επεκτείνουμε τον τύπο F_n=\frac{\alpha^n - \beta^n}{\sqrt{5}} και για αρνητικές τιμές του n νομίζω ότι είναι αρκετό (και πάρα πολύ καλή ιδέα!).


"Υπάρχει αρκετό φως γι' αυτούς που επιθυμούν να δουν και αρκετό σκοτάδι γι' αυτούς που έχουν την αντίθετη επιθυμία", B. Pascal
Άβαταρ μέλους
Demetres
Γενικός Συντονιστής
Δημοσιεύσεις: 8615
Εγγραφή: Δευ Ιαν 19, 2009 5:16 pm
Τοποθεσία: Λεμεσός/Πύλα
Επικοινωνία:

Re: Fibonacci, what else?

#6

Μη αναγνωσμένη δημοσίευση από Demetres » Δευ Ιαν 04, 2021 11:16 am

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}.
Σαφώς και έχεις δίκαιο. :oops:


Απάντηση

Επιστροφή σε “ΘΕΩΡΙΑ ΑΡΙΘΜΩΝ”

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

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 1 επισκέπτης