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

TrItOs · #1

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

Πρόβλημα : Θεωρούμε τους θετικούς ακέραιους αριθμούς $\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}$

llenny · #2

Στο προηγούμενο post είχα διαβάσει λάθος την άσκηση, νομίζω έχω μία λύση αλλά θα μου πάρει κάμποσο να την τσεκάρω και να τη γράψω σε LATEX, διότι τώρα μαθαίνω. Πάλι λάθος είμαι οπότε όποιος μπορεί ας βοηθήσει γιατί δε φαίνεται να μπορώ ακόμα να βοηθήσω ο ίδιος.

TrItOs · #3

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

Θα ηθέλα να με βοηθήσεις στα ερώτηματα που θέτω, αν γίνεται.

llenny · #4

Λάθος.

TrItOs · #5

Σχολιάζω ότι δεν έχει αποδειχθεί ακόμα ότι ο αριθμός $\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 · #6

Πάλι λάθος.

TrItOs · #7

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

k=3

υπάρχουν άπειρα ζεύγη της μορφής $\big(3 \cdot a - 1 - b, a \big)$ με αρχικό ζεύγος (a,b)=(2,2)

και έπειτα με διαδοχικές επαναλήψεις έχουμε : (2,2), (3,2), (6,3), (14,6), (35,14), . . .

και

υπάρχουν άπειρα ζεύγη της μορφής $\big(4 \cdot a - 1 - b, a \big)$ με αρχικό ζεύγος (a,b)=(1,1)

και έπειτα με διαδοχικές επαναλήψεις έχουμε : (1,1), (2,1), (6,2), (21,6), (77,21), . . .

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

llenny · #8

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

και το έβαλα και στη διακρίνουσα.

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

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

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

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

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

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

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

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

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

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