Let $a_1,a_2$ - two naturals, and $1<b_1<a_1,1<b_2<a_2$ and $b_1|a_1,b_2|a_2$. Prove that $a_1b_1+a_2b_2-1$ is not divided by $a_1a_2$
Problem
Source: St Petersburg Olympiad 2013, Grade 10, P7
Tags: number theory
21.05.2019 02:24
Funny Vieta jumping problem! Assume, for contradiction, that there existed such positive integers $1 \le b_1 < a_1, 1 \le b_2 < a_2$ with $b_1|a_1, b_2|a_2,$ and $a_1a_2| a_1b_1 + a_2b_2 -1$. Then, among such quadruples of positive integers, take the one $(a_1, a_2, b_1, b_2)$ which attained the smallest possible value of $a_1 + a_2$. If there are many, then take one arbitrarily. Let $d_1 = \frac{a_1}{b_1}, d_2 = \frac{a_2}{b_2}.$ By assumption, $d_1, d_2 > 1.$ We then know that there exists a positive integer $k$ for which $$\frac{a_1^2}{d_1} + \frac{a_2^2}{d_2} - 1 = ka_1a_2,$$which rewrites as $$d_2a_1^2 + d_1a_2^2 - d_1d_2 = ka_1a_2d_1d_2.$$WLOG, let's suppose by symmetry that $d_1a_2^2 \ge d_2a_1^2$. Then, let $x = \frac{d_2a_1^2 - d_1d_2}{d_1a_2} = ka_1d_2 - a_2.$ Note that $x>0$ since $d_2a_1^2 > d_2d_1^2 \ge d_2d_1.$ This is the "Vieta jump." We know that $$\frac{a_1^2}{d_1} + \frac{x^2}{d_2} - 1 = ka_1x$$is satisfied, so therefore we have that $(a_1, x, b_1, \frac{x}{d_2})$ is a functional quadruple as well (since $d_2|a_2 \Rightarrow d_2|ka_1d_2 - a_2=x$). However, since $d_2a_1^2 \le d_1a_2^2$, we have that $x = \frac{d_2a_1^2 - d_1d_2}{d_1a_2} \le \frac{d_1a_2^2 - d_1d_2}{d_1a_2} < \frac{d_1a_2^2}{d_1a_2} = a_2$, which implies that $a_1 + x < a_1 + a_2.$ However, this contradicts the assumption on the minimality of $a_1 + a_2$ which we made earlier, and hence our initial assumption that there existed such quadruples $(a_1, a_2, b_1, b_2)$ was incorrect. $\square$
21.05.2019 13:02
I have solved the problem with out using vieta jumping
21.05.2019 13:05
21.05.2019 20:21
@above Sorry, the problem asks us to show that $a_1a_2 \nmid a_1b_1 + a_2b_2 - 1$, not $a_1b_2 + a_2b_1 - 1$. This means that size considerations are probably not helpful, since we could have $b_1 >>>a_2$, for example.