$\textbf{N6.}$ Let $a,b$ be positive integers. If $a,b$ satisfy that \begin{align*} \frac{a+1}{b} + \frac{b+1}{a} \end{align*}is also a positive integer, show that \begin{align*} \frac{a+b}{gcd(a,b)^2} \end{align*}is a Fibonacci number. Proposed by usjl
Problem
Source: IMOC 2020
Tags: number theory, greatest common divisor, IMOC
Gaussian_cyber
05.09.2020 10:21
Wlog $a>b$ If they are equal it's obvious. The problem is equivalent to $a^2+b^2+a+b-kab=0$ see this as quadratic for $a$ Then $a_2$ is the other root. $a + a_2 = bk-1 \implies a_2 \in \mathbb{Z}$ $a a_2 = b^2+b \implies a_2 \in \mathbb{N} , a_2 \leq b$ So we got a tuple $(b,a_2)$ with smaller sum except they are equal. So get the tuple with smallest sum named $(a,b)$ according to above we should have $a=b$. Then $a=2 or 1$ $\textbf{Case 1.}$ $a=2 , k=3$ Then we have the previous answer in our descend was $(3a-1-b , a)$ that is $(3,2)$ , $(6,3)$ , $(14,6) , \dots$ and these all work. $\textbf{Case 2.}$ $a=1 , k=4$ Then the previous answer in our descend was $(4a-1-b,a)$ , So we find $(1,1),(2,1),(6,2),(21,6),\dots$ and they all work. Now I should just prove that they work is the second relation: For the first case I prove it becomes 5,1 alternatively I'll post the rest 4 hours later[my class began lol]
WolfusA
05.09.2020 10:42
Yes Tintarn, now everything is right. #1731
Tintarn
05.09.2020 14:03
@above: I hope the edit makes it clear? It is just standard Vieta jumping anyway... To finish, in Case 2, it is similarly easy to prove that the quotient becomes $2$ and $3$ alternatingly. So, funnily enough, although the problem is actually related to Fibonacci numbers (since the sequences of solutions clearly are), the actual problem statement is a bit of a red herring, since the eventual set of values is just $\{1,2,3,5\}$ which happens to be a subset of the Fibonacci sequence...
naman12
05.09.2020 19:07
Oops I fell asleep before I finished typing this up.
We'll Vieta jump to $a=b$. Note in this case $a=b\in\{1,2\}$. Now, if $a>b$, we note that if
\[\frac{a+1}b+\frac{b+1}a=k\]then
\[x^2-(kb-1)x+b^2+b=0\]has a root at $x=a$, so the other is at $x=kb-1-a=\frac{b^2+b}a$. Note that $0<\frac{b^2+b}a<b$, so thus we can endlessly jump until we reach $a=b$, or $k=3,4$. Now, we'll first characterize the sequence satisfying
\[a_n=ka_{n-1}-a_{n-2}=\frac{a_{n-1}^2+a_{n-1}}{a_{n-2}}\]In particular, we'll characterize
\[d_n=\gcd(a_n,a_{n+1})\]First, we claim that
\[d_nd_{n-1}=a_n\]This is clear, because
\[d_n=\gcd(a_n,a_{n+1})=\gcd\left(a_n,\frac{a_n(a_n+1)}{a_{n-1}}\right)=\gcd\left(a_n,\frac{a_n}{a_{n-1}}\right)=\frac{a_n}{\gcd(a_n,a_{n-1})}=\frac{a_n}{d_{n-1}}\]Next, we show that $d_n=\frac{a_n}{a_{n-1}}d_{n-2}$. This is also clear, as
\[\frac{d_n}{d_{n-2}}=\frac{d_nd_{n-1}}{d_{n-1}d_{n-2}}=\frac{a_n}{a_{n-1}}\]Finally, we'll show $d_n=kd_{n-2}-d_{n-4}$. This lastly is clear because
\[d_n-kd_{n-2}+d_{n-4}=d_{n-4}\left(\frac{a_na_{n-2}}{a_{n-1}a_{n-3}}-\frac{ka_{n-2}}{a_{n-3}}+1\right)=d_{n-4}\left(\frac{a_na_{n-2}-ka_{n-1}a_{n-2}+a_{n-1}a_{n-3}}{a_{n-1}a_{n-3}}\right)\]However, this is clear, as
\[0=a_{n-1}a_{n-3}-a_{n-2}^2-a_{n-2}=a_na_{n-2}-ka_{n-1}a_{n-2}+a_{n-1}a_{n-3}\]Finally, the main problem - we can compute
\[f_n=\frac{a_n+a_{n+1}}{d_n^2}=\frac{d_{n-1}+d_{n+1}}{d_n}=\frac{5d_{n-1}-d_{n-3}}{4d_{n-2}-d_{n-4}}\]If we know
\[f_{n-2}=f_{n-4}=f\]then
\[\frac{4d_{n-1}+4d_{n-3}}{4d_{n-2}}=\frac{d_{n-3}+d_{n-5}}{d_{n-4}}=f\]implying
\[f=\frac{4d_{n-1}+4d_{n-3}-d_{n-3}-d_{n-5}}{4d_{n-2}-d_{n-4}}=\frac{5d_{n-1}-d_{n-3}}{4d_{n-2}-d_{n-4}}\]Now, we'll turn to the specific cases $k=3,4$. For $k=3$, we get that $a_1=2,a_2=2,a_3=3,a_4=6,a_5=14$, so thus $f_1=f_3=1$, $f_2=f_4=5$, and thus $f_{2k+1}=1$ while $f_{2k}=5$. Similarly, if $k=4$, we get that $a_1=1,a_2=1,a_3=2,a_4=6,a_5=21$, so thus $f_1=f_3=2$, $f_2=f_4=3$, and thus again $f_{2k+1}=2$ while $f_{2k}=3$. This not only shows the claim, but also the number must be in $\{1,2,3,5\}$.
USJL
11.09.2020 13:30
One generalization that I think is true but haven't had time to prove is that when both 1's are replaced by $k$'s where $k$ is a given positive integer, there are only finitely many possible values for $(a+b) ^2/\gcd(a,b)^2$.
individ
12.09.2020 07:48
https://artofproblemsolving.com/community/c3046h1046790___ https://artofproblemsolving.com/community/c3046h1046791__ https://artofproblemsolving.com/community/c3046h1046841___
me9hanics
22.11.2020 17:03
Tintarn wrote: @above: I hope the edit makes it clear? It is just standard Vieta jumping anyway... To finish, in Case 2, it is similarly easy to prove that the quotient becomes $2$ and $3$ alternatingly. So, funnily enough, although the problem is actually related to Fibonacci numbers (since the sequences of solutions clearly are), the actual problem statement is a bit of a red herring, since the eventual set of values is just $\{1,2,3,5\}$ which happens to be a subset of the Fibonacci sequence... I agree, it mislead me, at first I thought "Hmm.. for any $a$ number only those $b$ values can satisfy for which their sum is a Fibonacci number times a square number..." Then after some time, I realized, maybe it just has finite solutions, and Vieta lead to those solutions and I was disappointed, since the solutions just "luckily" satisfy the condition, have no fundamental relation to the Fibonacci-sequence.
USJL
19.12.2020 10:49
misinnyo wrote: Tintarn wrote: @above: I hope the edit makes it clear? It is just standard Vieta jumping anyway... To finish, in Case 2, it is similarly easy to prove that the quotient becomes $2$ and $3$ alternatingly. So, funnily enough, although the problem is actually related to Fibonacci numbers (since the sequences of solutions clearly are), the actual problem statement is a bit of a red herring, since the eventual set of values is just $\{1,2,3,5\}$ which happens to be a subset of the Fibonacci sequence... I agree, it mislead me, at first I thought "Hmm.. for any $a$ number only those $b$ values can satisfy for which their sum is a Fibonacci number times a square number..." Then after some time, I realized, maybe it just has finite solutions, and Vieta lead to those solutions and I was disappointed, since the solutions just "luckily" satisfy the condition, have no fundamental relation to the Fibonacci-sequence. Yeah the intention is to troll the students a bit :p (I mean it's a camp and I also want to have some fun(X)) But yeah it has nothing to do with the Fibonacci sequence. I just got the solutions $1,2,3,5$ and be like, hey, they all happen to be Fibonacci numbers! If $1$ weren't a solution, I would have probably asked them to prove that the number has to be a prime :p.
lazizbek42
02.01.2022 07:06
Vieta jumping and pell equation