Fibonacci και Μέγιστος Κοινός Διαιρέτης

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

TrItOs
Δημοσιεύσεις: 53
Εγγραφή: Τρί Ιουν 09, 2015 6:50 pm

Fibonacci και Μέγιστος Κοινός Διαιρέτης

#1

Μη αναγνωσμένη δημοσίευση από TrItOs » Τετ Δεκ 23, 2020 12:15 pm

Παραθέτω παρακάτω ένα πρόβλημα, στο οποίο έχω "κολλήσει" σε ένα σημείο και τονίζω τα σημεία, και γενικά να μου πείτε εάν είναι σωστή. Θα ήθελα την βοήθειά σας. Ευχαριστώ.

Πρόβλημα : Θεωρούμε τους θετικούς ακέραιους αριθμούς \displaystyle{a, b} τέτοιους ώστε να ικανοποιούν την συνθήκη ότι ο αριθμός \displaystyle{\frac{a+1}{b} + \frac{b+1}{a}} είναι επίσης θετικός ακέραιος. Τότε να δειχθεί ότι ο αριθμός \displaystyle{\frac{a + b}{ \gcd{ (a, b)^{2}}}} είναι αριθμός \displaystyle{Fibonacci}.

Λύση

Αρχικά μπορούμε να υποθέσουμε χωρίς βλάβη της γενικότητας \displaystyle{a \geqslant b}. Tότε έχουμε τις εξής δύο περιπτώσεις

Αν \displaystyle{a = b} τότε προκύπτει ότι
\mathbb{N} \ni \frac{a+1}{a} + \frac{a+1}{a} = 2 \cdot \frac{a+1}{a} \Rightarrow a \big| 2 \cdot (a+1) \Rightarrow a \big| 2 \cdot (a+1) - 2 \cdot a = 2 \Rightarrow a = 1 ή a = 2

, και τότε για \displaystyle{a = b = 1} είναι \displaystyle{\frac{a + b}{\gcd{(a, b)^{2}}} = \frac{1 + 1}{\gcd(1, 1)^{2}}} = 2 = f_{3}}, επιπλέον για \displaystyle{a = b = 2} είναι \displaystyle{\frac{a + b}{\gcd(a, b)^{2}}} = \frac{2 + 2}{\gcd(2, 2)^{2}}} = 1 = f_{2}}.

Αν \displaystyle{a > b} και άρα \displaystyle{a > b \geqslant 1 \Rightarrow a \geqslant b + 1} τότε εξ' υποθέσεως έχουμε ότι υπάρχει θετικός ακέραιος \displaystyle{k} τέτοιος ώστε \displaystyle{\frac{a+1}{b} + \frac{b+1}{a} = k} τότε ισοδύναμα έχουμε ότι:
(a+1) \cdot a + (b+1) \cdot b = k \cdot a \cdot b \Leftrightarrow a^{2} + a + b^{2} + b - k \cdot a \cdot b = 0 \Leftrightarrow \boxed{a^{2} + \big( 1 - b \cdot k \big) \cdot a + b^{2} + b = 0. \text{ } (1)}

Έπειτα η σχέση (1) μας οδηγεί στο να θεωρήσουμε την δευτεροβάθμια εξίσωση (τριώνυμο) \displaystyle{\boxed{x^{2} + \big( 1 - b \cdot k \big) \cdot x + b^{2} + b = 0. \text{ } (2)}}, την οποία επιλύουμε ως προς το \displaystyle{x}. Λόγω της σχέσης (1) έχουμε ότι η δευτεροβαθμία εξίσωση (2) έχει μια λύση η οποία είναι η \displaystyle{x_{1} = a} και μια δεύτερη λύση την \displaystyle{x_{2} = a_{1}}, τότε από τους τύπους \displaystyle{Vieta} έχουμε ότι \displaystyle{x_{1} + x_{2} = b \cdot k - 1 \Rightarrow \boxed{a + a_{1} = b \cdot k - 1}} και \displaystyle{x_{1} \cdot x_{2} = b^{2} + b \Rightarrow \boxed{a \cdot a_{1} = b^{2} + b}}, τότε προκύπτει ότι \displaystyle{a_{1} = b \cdot k - 1 - a \in \mathbb{Z}}, και επειδή \displaystyle{a \cdot a_{1} = b^{2} + b \in \mathbb{N} \Rightarrow a, b^{2} + b \in \mathbb{N} \Rightarrow \boxed{a_{1} \in \mathbb{N}. \text{ } (3)}} και άρα \displaystyle{a_{1} = \frac{b^{2} + b}{a} \leqslant \frac{b^{2} + b}{b + 1} = b \Rightarrow \boxed{a_{1} \leqslant b . \text{ } (4)}}, σημειώνουμε ότι το \displaystyle{a_{1} \in \mathbb{N}} ικανοποιεί την εξίσωση (1), δηλαδή έχουμε ότι \displaystyle{\frac{a_{1}+1}{b} + \frac{b+1}{a_{1}} = k \in \mathbb{N}}, τότε αν υποθέσουμε ότι το ζεύγος \displaystyle{(a, b) \in \mathbb{N} \times \mathbb{N}} έχει το μικρότερο δυνατό άθροισμα ώστε ο αριθμός \displaystyle{\frac{a+1}{b} + \frac{b+1}{a}} να είναι θετικός ακέραιος, τότε υπάρχει το ζεύγος \displaystyle{(a_{1}, b ) \in \mathbb{N} \times \mathbb{N}} ώστε να ισχύει πως ο αριθμός \displaystyle{\frac{a_{1} + 1}{b} + \frac{b + 1}{a_{1}}} να είναι θετικός ακέραιος με την ιδιότητα ότι \displaystyle{a_{1} \leqslant b \Rightarrow a + a_{1} \leqslant a + b}, το οποίο μας οδηγεί στο ότι πρέπει να ισχύει \displaystyle{a_{1} = b}. Δηλαδή το σύνολο \displaystyle{S = \Big \{ (a, b) \in \mathbb{N} \times \mathbb{N} : \frac{a+1}{b} + \frac{b+1}{a} \in \mathbb{N} \Big \}} είναι μη κενό και υπάρχει ζεύγος \displaystyle{(a, b) \in \mathbb{N} \times \mathbb{N}} με \displaystyle{(a, b) \in S} ώστε το \displaystyle{a+b} να είναι το ελάχιστο δυνατό μόνο στην περίπτωση που ισχύει ότι \displaystyle{a_{1} = b}, τότε όμως θα ικανοποιείται η σχέση \displaystyle{a = b \cdot k - 1 - b} και \displaystyle{a = b + 1} και άρα θα πρέπει \displaystyle{b = 1 \Rightarrow a = 2, k = 4} ή \displaystyle{b = 2 \Rightarrow a = 3, k = 3}.

Συμπέρασμα : Δοθέντος ενός ζεύγους \displaystyle{(a, b) \in S}, με \displaystyle{a > b}, προκύπτει ο αριθμός \displaystyle{k = \frac{a+1}{b} + \frac{b+1}{a} \in \mathbb{N}}, όπου για αυτόν τον αριθμό \displaystyle{k} αντιστοιχεί ένα ζεύγος \displaystyle{(a_{1}, b) \in S} με ελάχιστο άθροισμα, όπου τελικά για το ζεύγος με το ελάχιστο άθροισμα ισχύει \displaystyle{a_{1} = b} και οπότε \displaystyle{(b, b) \in S \Rightarrow b = 1 ή b = 2}. Οπότε οι μόνες δυνατές τιμές του \displaystyle{k} είναι \displaystyle{3} ή \displaystyle{4}.


Τότε αν \displaystyle{\big( a, b \big) = S = \Big \{ \big( a, b \big) \in \mathbb{N} \times \mathbb{N} : \frac{a+1}{b} + \frac{b+1}{a} = k \in \mathbb{N} \Big \} } προκύπτει ότι ή

\displaystyle{k = 3} : και άρα θα είναι \displaystyle{\frac{a+1}{b} + \frac{b+1}{a} = 3 \Leftrightarrow a^{2} + a + b^{2} + b = 3 \cdot a \cdot b} και ας είναι \displaystyle{d = \gcd{ \big( a, b \big)}}, τότε \displaystyle{d \big| a \Rightarrow \exists a_{1} \in \mathbb{N} : a = a_{1} \cdot d} και \displaystyle{d \big| b \Rightarrow \exists b_{1} \in \mathbb{N} : b = b_{1} \cdot d} και τότε είναι \displaystyle{a_{1}^{2} \cdot d^{2} + a_{1} \cdot d + b_{1}^{2} \cdot d^{2} + b_{1} \cdot d = 3 \cdot a_{1} \cdot b_{1} \cdot d^{2}} οπότε ισοδύναμα έχουμε ότι \displaystyle{a_{1}^{2} \cdot d + a_{1} + b_{1}^{2} \cdot d + b_{1} = 3 \cdot a_{1} \cdot b_{1} \cdot d}, και θέλουμε να υπολογίσουμε το \displaystyle{\frac{a+b}{\gcd{ \big( a, b \big)^{2}}} = \frac{a_{1} \cdot d + b_{1} \cdot d}{d^{2}} = \frac{a_{1} + b_{1}}{d}}, (ΠΩΣ ΑΠΟΔΕΙΚΝΎΕΤΑΙ ΌΤΙ ΕΊΝΑΙ ΑΡΙΘΜΌΣ Fibonacci ;)

ή

\displaystyle{k = 4} : και άρα θα είναι \displaystyle{\frac{a+1}{b} + \frac{b+1}{a} = 4 \Leftrightarrow a^{2} + a + b^{2} + b = 4 \cdot a \cdot b} και ας είναι \displaystyle{d = \gcd{ \big( a, b \big)}}, τότε \displaystyle{d \big| a \Rightarrow \exists a_{2} \in \mathbb{N} : a = a_{2} \cdot d} και \displaystyle{d \big| b \Rightarrow \exists b_{2} \in \mathbb{N} : b = b_{2} \cdot d} και τότε είναι \displaystyle{a_{2}^{2} \cdot d^{2} + a_{2} \cdot d + b_{2}^{2} \cdot d^{2} + b_{2} \cdot d = 3 \cdot a_{2} \cdot b_{2} \cdot d^{2}} οπότε ισοδύναμα έχουμε ότι \displaystyle{a_{2}^{2} \cdot d + a_{2} + b_{2}^{2} \cdot d + b_{2} = 3 \cdot a_{2} \cdot b_{2} \cdot d}, και θέλουμε να υπολογίσουμε το \displaystyle{\frac{a+b}{\gcd{ \big( a, b \big)^{2}}} = \frac{a_{2} \cdot d + b_{2} \cdot d}{d^{2}} = \frac{a_{2} + b_{2}}{d}}, (ΠΩΣ ΑΠΟΔΕΙΚΝΎΕΤΑΙ ΌΤΙ ΕΊΝΑΙ ΑΡΙΘΜΌΣ Fibonacci ;)

Ερώτημα :

(1) Αν  \displaystyle{a = f_{2 \cdot n - 1} + 1, b = f_{2 \cdot n + 1} + 1 \in \mathbb{S}} με  \displaystyle{\frac{a+1}{b} + \frac{b+1}{a} = 3} ή ισοδύναμα προκύπτει ότι για  \displaystyle{a = \frac{x + 2 + y}{2} \text{ } , \text{ } b = \frac{x + 2 - y}{2}} έχουμε ότι  \displaystyle{ x^{2} - 5 \cdot y^{2} = 4 } αλλά πως προκύπτει ότι ο αριθμός  \displaystyle{\frac{a + b}{\gcd{\big( a, b \big)^{2}}}} = \frac{f_{2 \cdot n - 1} + f_{2 \cdot n + 1} + 2}{\gcd{\big( f_{2 \cdot n -1} + 1, f_{2 \cdot n + 1} + 1 \big)^{2}}} = \cdots} είναι αριθμός  \displaystyle{Fibonacci} ;

(2) Αν  \displaystyle{a, b \in \mathbb{S}} με  \displaystyle{\frac{a+1}{b} + \frac{b+1}{a} = 4} (υπάρχει κάποια αντίστοιχη γραφεί με αυτή στο Ερώτημα (1), παρατηρείτε κάτι τέτοιο ;) ή ισοδύναμα προκύπτει ότι για  \displaystyle{a = \frac{x + 1 + y}{2} \text{ } , \text{ } b = \frac{x + 1 - y}{2}} έχουμε ότι  \displaystyle{ x^{2} - 3 \cdot y^{2} = 1 } αλλά πως προκύπτει ότι ο αριθμός  \displaystyle{\frac{a + b}{\gcd{\big( a, b \big)^{2}}}}} είναι αριθμός  \displaystyle{Fibonacci} ;
τελευταία επεξεργασία από TrItOs σε Πέμ Δεκ 31, 2020 12:44 am, έχει επεξεργασθεί 1 φορά συνολικά.



Λέξεις Κλειδιά:
Άβαταρ μέλους
llenny
Δημοσιεύσεις: 47
Εγγραφή: Τρί Απρ 23, 2019 11:10 pm
Τοποθεσία: Σητεία Κρήτης

Re: Fibonacci και Μέγιστος Κοινός Διαιρέτης

#2

Μη αναγνωσμένη δημοσίευση από llenny » Τετ Δεκ 23, 2020 12:43 pm

Στο προηγούμενο post είχα διαβάσει λάθος την άσκηση, νομίζω έχω μία λύση αλλά θα μου πάρει κάμποσο να την τσεκάρω και να τη γράψω σε LATEX, διότι τώρα μαθαίνω. Πάλι λάθος είμαι οπότε όποιος μπορεί ας βοηθήσει γιατί δε φαίνεται να μπορώ ακόμα να βοηθήσω ο ίδιος.
τελευταία επεξεργασία από llenny σε Τετ Δεκ 23, 2020 1:12 pm, έχει επεξεργασθεί 1 φορά συνολικά.


TrItOs
Δημοσιεύσεις: 53
Εγγραφή: Τρί Ιουν 09, 2015 6:50 pm

Re: Fibonacci και Μέγιστος Κοινός Διαιρέτης

#3

Μη αναγνωσμένη δημοσίευση από TrItOs » Τετ Δεκ 23, 2020 12:53 pm

llenny έγραψε:
Τετ Δεκ 23, 2020 12:43 pm
Στο προηγούμενο post είχα διαβάσει λάθος την άσκηση, νομίζω έχω μία λύση αλλά θα μου πάρει κάμποσο να την τσεκάρω και να τη γράψω σε LATEX, διότι τώρα μαθαίνω.
Θα ηθέλα να με βοηθήσεις στα ερώτηματα που θέτω, αν γίνεται.


Άβαταρ μέλους
llenny
Δημοσιεύσεις: 47
Εγγραφή: Τρί Απρ 23, 2019 11:10 pm
Τοποθεσία: Σητεία Κρήτης

Re: Fibonacci και Μέγιστος Κοινός Διαιρέτης

#4

Μη αναγνωσμένη δημοσίευση από llenny » Τετ Δεκ 23, 2020 2:34 pm

Λάθος.
τελευταία επεξεργασία από llenny σε Τετ Δεκ 23, 2020 4:43 pm, έχει επεξεργασθεί 2 φορές συνολικά.


TrItOs
Δημοσιεύσεις: 53
Εγγραφή: Τρί Ιουν 09, 2015 6:50 pm

Re: Fibonacci και Μέγιστος Κοινός Διαιρέτης

#5

Μη αναγνωσμένη δημοσίευση από TrItOs » Τετ Δεκ 23, 2020 4:12 pm

Σχολιάζω ότι δεν έχει αποδειχθεί ακόμα ότι ο αριθμός \frac{a+b}{\gcd{(a,b)^{2}}} είναι Fibonacci αν ισχύει ότι \frac{a+1}{b}+\frac{b+1}{a}=3 ή \frac{a+1}{b}+\frac{b+1}{a}=4


Άβαταρ μέλους
llenny
Δημοσιεύσεις: 47
Εγγραφή: Τρί Απρ 23, 2019 11:10 pm
Τοποθεσία: Σητεία Κρήτης

Re: Fibonacci και Μέγιστος Κοινός Διαιρέτης

#6

Μη αναγνωσμένη δημοσίευση από llenny » Τετ Δεκ 23, 2020 4:18 pm

Πάλι λάθος.
τελευταία επεξεργασία από llenny σε Τετ Δεκ 23, 2020 4:44 pm, έχει επεξεργασθεί 1 φορά συνολικά.


TrItOs
Δημοσιεύσεις: 53
Εγγραφή: Τρί Ιουν 09, 2015 6:50 pm

Re: Fibonacci και Μέγιστος Κοινός Διαιρέτης

#7

Μη αναγνωσμένη δημοσίευση από TrItOs » Τετ Δεκ 23, 2020 4:37 pm

Παρατήρησε ότι για

k=3 υπάρχουν άπειρα ζεύγη της μορφής \big(3 \cdot a - 1 - b, a \big) με αρχικό ζεύγος (a,b)=(2,2) και έπειτα με διαδοχικές επαναλήψεις έχουμε : (2,2), (3,2), (6,3), (14,6), (35,14), . . .

και

k=4 υπάρχουν άπειρα ζεύγη της μορφής \big(4 \cdot a - 1 - b, a \big) με αρχικό ζεύγος (a,b)=(1,1) και έπειτα με διαδοχικές επαναλήψεις έχουμε : (1,1), (2,1), (6,2), (21,6), (77,21), . . .

όπου ικανοποιούν το συμπέρασμα που θέλουμε. Αλλά το ερώτημα είναι το πως το δείχνουμε αυτό ;


Άβαταρ μέλους
llenny
Δημοσιεύσεις: 47
Εγγραφή: Τρί Απρ 23, 2019 11:10 pm
Τοποθεσία: Σητεία Κρήτης

Re: Fibonacci και Μέγιστος Κοινός Διαιρέτης

#8

Μη αναγνωσμένη δημοσίευση από llenny » Τετ Δεκ 23, 2020 4:44 pm

Έχεις δίκιο, είχα λάθος. Προσπάθησα να αναπαράξω τη λύση απο παρόμοια άσκηση στο AOPS για εξάσκηση στο Vieta Jumping και στη LATEX αλλά μου είχε μείνει στο μυαλό του 5αρι που είχε συντελεστή στο ab και το έβαλα και στη διακρίνουσα. :(


Απάντηση

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

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

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