Suppose that $a,b$ are two odd positive integers such that $2ab+1 \mid a^2 + b^2 + 1$. Prove that $a=b$. (15 points)
Problem
Source: Iran 3rd round 2013 - Number Theory Exam - Problem 2
Tags: algebra, polynomial, Vieta, number theory proposed, number theory, Vieta Jumping
11.09.2013 18:05
Vieta jumping kills it. There might exist less OP methods to solve it, though.
11.09.2013 18:19
goldeneagle wrote: Suppose that $a,b$ are two odd positive integers such that $2ab+1 \mid a^2 + b^2 + 1$. Prove that $a=b$. (15 points) Let $\frac{a^2+b^2+1}{2ab+1}=k$ with $k \in \mathbb{N}^*$. Hence $a^2+b^2-2abk+1-k=0 \qquad (1)$. Let $(a_0,b_0)$ be the root such that $a_0+b_0$ is minimum. Without loss of generality, assume that $a_0 \le b_0$. Considering the equation \[x^2-2a_0k \cdot x+a_0^2-k+1=0\] It follows that $b_0$ is a solution of the equation. Let $b_1$ be the other solution. Since $(a_0,b_1)$ is also a root of the equation $(1)$ then $a_0+b_0 \le a_0+b_1$ implies $b_0 \le b_1$. By Vieta theorem we have $\begin{cases} b_0+b_1= 2a_0k \\ b_0 \cdot b_1= a_0^2-k+1 \end{cases}$. $\blacktriangleright$ Case 1. If $a_0=b_0$ then $k= \frac{2a_0^2+1}{2a_0^2+1}=1$. Hence $a^2+b^2+1=2ab$ implies $a=b$. $\blacktriangleright$ Case 2. If $b_1=b_0$ then $b_0^2=a_0^2-k+1$ or $\left( a_0-b_0\right) \left( a_0+b_0 \right)=1-k$. Since $k \in \mathbb{N}^*$ then $a_0=b_0$. Thus, $a=b$. $\blacktriangleright$ Case 3. If $a_0<b_0<b_1$ then $b_0 \ge a_0+1$ and $b_1 \ge a_0+2$. It follows that \[a_0^2-k+1=b_0 \cdot b_1 \ge \left( a_0+1 \right) \left( a_0+2 \right) \Rightarrow 1-k \ge 3a_0+2,\] a contradiction since $3a_0+2 \ge 2 >1-k$. Thus, $\boxed{a=b}$.
14.09.2013 13:13
my solution is by Vieta Jumping too!
14.09.2013 16:42
shinichiman wrote: then $a_0+b_0 \le a_0+b_1$ I think you are wrong, because $ b_1 $ might be negative and it wouldn't be a solution in positive integers. Also we have to use the fact that $ a $ and $ b $ are odd because otherwise the statement is not true (for example, $ (a,b)=(2,20) $).
14.09.2013 19:24
Let $\dfrac{a^2+b^2+1}{2ab+1}=k$ with $k \in \mathbb{N}^*$, hence $a^2+b^2-2abk+1-k=0$. Assume $(a,b)$ to be a solution in positive integers with $a\neq b$. Denote $\alpha = \min\{a,b\}$, $\beta = \max\{a,b\}$. Thus $(\alpha,\beta)$ is a solution, with $\alpha < \beta$. Considering the equation \[x^2-2\alpha kx+\alpha^2-k+1=0,\] it follows that $\beta$ is a solution of the equation. Let $\gamma$ be the other solution. By the Vieta relations we have $\begin{cases} \beta +\gamma = 2\alpha k \\ \beta\gamma = \alpha^2-k+1 \end{cases}$. Thus $\gamma = 2\alpha k-\beta$ is integer. But then we have $0 < \gamma^2 + \alpha^2 + 1 = k(2\alpha\gamma+1)$, so we must have $\gamma\geq 0$ (if $\gamma\leq -1$ we would have $k(2\alpha\gamma +1) \leq k(-2\alpha+1) < 0$). When $\beta$ is odd it follows $\gamma$ is also odd, thus $\gamma=0$ is impossible, so $\gamma>0$. Finally, since then $0< \beta\gamma = \alpha^2-k+1 \leq \alpha^2$ and $\beta >\alpha$, it follows $\gamma < \alpha$. By the method of Vieta jumping (in fact a case of the infinite descent method), we can now repeat the above, with $(\alpha', \beta') = (\gamma, \alpha)$ (when $\alpha$ is also odd, since already $\gamma$ has been proved odd, and so this parity perpetuates), and this leads to a typical contradiction. Notice that for $a=b$ we have $\dfrac{a^2+b^2+1}{2ab+1} = 1$, an identity alwys true. Thus the problem with the proof proposed above is not in the fact that $b_1$ might be negative (which was shown to be impossible since my $\gamma$ plays the role of the $b_1$), but in not using the parity of the integers involved, and also in only providing a result for the minimal solution $(a_0,b_0)$, showing that it forces $a_0=b_0$, but leaving open a possibility with $a<b$ and $(a,b)$ not minimal. For good measure let us also analyse what happens if $a,b$ might be even. Everything works the same, up to the point where we could have $\gamma = 0$. That would force $\alpha^2 = k-1$, so $k=\alpha^2+1$, with an initial solution $(a_0,b_0) = (0,\alpha)$ which is unacceptable, since containing $0$, but which generates the infinite family of solutions $(a_n,b_n)\mapsto (a_{n+1},b_{n+1})$ via $a_{n+1} = b_n$, $b_{n+1} = 2kb_n - a_n$ for all $n\geq 0$. Thus the problem only has solutions $a\neq b$ when $k$ is one more than a perfect square (and then one of $a,b$ or both are even). For example $\bullet$ for $\alpha=1$ we have $k=2$ and solutions $(0,1)\mapsto (1,4)\mapsto (4,15) \mapsto \cdots$ $\bullet$ for $\alpha=2$ we have $k=5$ and solutions $(0,2)\mapsto (2,20)\mapsto (20,198) \mapsto \cdots$, which is the example given in the previous post.
15.09.2013 03:11
$a,b$ is two odd positive integers ??
15.09.2013 19:25
My solution takes care of all parity cases, if you just read it carefully.
15.09.2013 19:28
lawsy wrote: shinichiman wrote: then $a_0+b_0 \le a_0+b_1$ I think you are wrong, because $ b_1 $ might be negative and it wouldn't be a solution in positive integers. Also we have to use the fact that $ a $ and $ b $ are odd because otherwise the statement is not true (for example, $ (a,b)=(2,20) $). I still don't understand why $b_1$ might be negative. Could you please explain to me ?? Thank you very much.
15.09.2013 19:32
Oh, please, read the above posts. I already dealt with this issue, proving that it cannot be negative.
06.09.2014 21:15
Note that $2ab+1 \mid a^2+b^2+1 \Rightarrow 2ab+1 \mid (a-b)^2$. We now consider the positive integer solution set $(a,b)$ to the equation $\frac{(a-b)^2}{2ab+1}=k$ where $k$ is a fixed positive integer. Let $(a_0,b_0)$ be a solution for which the sum is minimal over all elements of the solution set.Without loss of generality let $a_0>b_0$.Now we consider another equation $\frac{(x-b_0)^2}{2xb_0+1}=k \Leftrightarrow x^2-2xb_0(k+1)+{b_0}^2-k=0$. Obviously one of the roots is $a_0$.The other root ${\alpha}_0=2b_0(k+1)-a_0$ is a positive integer.We can also say that ${\alpha}_0=\frac{{b_0}^2-k}{a_0}$.But $\frac{{b_0}^2-k}{a_0}<\frac{{b_0}^2}{a_0}<a_0 \Rightarrow a_0+b_0>a_0+{\alpha}_0$ a contradiction to our assumption.Thus $k=0$ and we are done.(Note that $k$ can't be negative). Is there no combinatorics exam??
30.12.2021 22:41
Let $(a,b)$ be the solution such that $a\neq b$ and $a+b$ is minimized; WLOG $a>b.$ Setting $\frac{a^2+b^2+1}{2ab+1}=k,$ we see that $$a^2-(2bk)a+(b^2-k+1)=0.\quad(*)$$Let $$a_1=2bk-a=\frac{b^2-k+1}{a}$$be the other solution to the quadratic $(*).$ Notice that $a_1=2bk-a$ is odd and we claim it is also positive; assume the contrary. Then, $a_1\le -1$ since $a_1$ is odd. Hence, $$0<a_1^2+b^2+1=(2a_1b+1)k\le (-2b+1)<0,$$a contradiction. Therefore, $(a_1,b)$ is also a solution, meaning $a_1\ge a.$ Thus, \begin{align*}a_1&=\frac{b^2-k+1}{a}\le\frac{b^2+1}{a}\\&\implies b^2+1\ge aa_1\ge a^2\ge (b+1)^2,\end{align*}which is absurd, so we conclude that $a=b$ for all solutions $(a,b).$ $\square$
28.12.2023 04:07
Assume there exists $a,b$ such that $a\neq b$ which satisfy the desired divisibility ($\frac{a^2+b^2+1}{2ab+1}=c>1$). We now consider the pair of odd positive integers $a,b$ such that $a+b$ is minimal and above condition is satisfied. Assume WLOG, $a\geq b$. Then, the quadratic \[X^2-2Xbc+b^2-c+1=0\]will have roots $a,a_1$. Note that $a+a_1=2bc$ (thus $a_1\in \mathbb{Z}$ ) and $aa_1=b^2-c+1$. Now, if $c \geq b^2+1$, \[a^2+b^2+1=c(2ab+1)\geq (b^2+1)(2ab+1)=2ab^3+b^2+2ab+1\]which implies that, $a\geq 2b^3+2b$ and since $a$ is odd, we have that, \[a>2b^3+2b\]Now, note that, $2ab+1 \mid a^2+b^2+1 \iff 2ab+1 \mid 2b^3+2b-a$ with some work using the Euclidean Algorithm. Since $a>2b^3+2b$, this implies that, \[a\geq 2ab+1+2b^3+2b>2ab>a\]which is a clear contradiction. Thus, $c<b^2+1$ and $a_1>0$. Further, this means \[2a\leq a+a_1=2bc \implies c\geq \frac{a}{b}\]But this means, \begin{align*} \frac{a^2+b^2+1}{2ab+1} &\geq \frac{a}{b}\\ b^3+b \geq a^2b+b \end{align*}But this implies that \[b^3+b \geq a^2b+b > b^3+b\](since we assumed that $a\neq b$), which is a clear contradiction. Thus, there cannot exist such a pair $a,b$ which implies that we must have $a=b$ as desired.
05.03.2024 23:55
WLOG $a\geq b$. Let $a=bk+r$ such that $0\leq r< b$. \[2b^2k+2br+1|2(bk-b+r)^2=2b^2k^2+2b^2+2r^2+4bkr-4b^2k-4br\]\[2b^2k+2br+1|2b^2k^2+2brk+k\]$\implies 2b^2k+2br+1|2b^2+2r^2+2bkr-4b^2k-4br-k$ Also $2b^2k+2br+1|4b^2k+4br+2$ $\implies 2b^2k+2br+1|2b^2+2r^2-k+2+2bkr\iff 2b^2k+2br+1|(2b^2+2r^2+2+2bkr)-k$ So \[P=\frac{(2b^2+2r^2+2+2bkr)-k}{2b^2k+2br+1}\geq 0\]is an integer.
06.03.2024 12:23
Redacted.
06.03.2024 14:24
Vulch wrote: My solution: $(a-b)^2=0$ implies that $a^2 +b^2=2ab.$ Or, $(a^2 +b^2 +1)=(2ab+1)\implies (a^2 +b^2 +1)/(2ab+1) =1.$ Which indicates that $(2ab+1)|(a^2 +b^2 +1).$ Therefore $(2ab+1)|(a^2 +b^2 +1)$ possible only when $(a+b)^2 =0$ i.e $a=b.$ Is this solution correct? You proved that $$a=b\implies 2ab+1\mid a^2+b^2+1.$$But the original question asks to prove the reverse i.e. $$2ab+1\mid a^2+b^2+1\implies a=b.$$
07.03.2024 04:09
\[2b^2k+2br+1|2b^2k^2+4brk+k\]???
07.03.2024 04:16
bin_sherlo wrote: WLOG $a\geq b$. Let $a=bk+r$ such that $0\leq r< b$. \[2b^2k+2br+1|2(bk-b+r)^2=2b^2k^2+2b^2+2r^2+4bkr-4b^2k-4br\]\[2b^2k+2br+1|2b^2k^2+4brk+k\]$\implies 2b^2k+2br+1|2b^2+2r^2-4b^2k-4br-k$ Also $2b^2k+2br+1|4b^2k+4br+2$ $\implies 2b^2k+2br+1|2b^2+2r^2-k+2\iff 2b^2k+2br+1|(2b^2+2r^2+2)-k$ $2b^2k+2br+k-2b^2-2r^2-1=k(2b^2+1)+2r(b-r)-(2b^2+1)=2r(b-r)+(k-1)(2b^2+1)\geq 0$ and equality holds when $k=1,r=0\iff a=b$. If $r>0,$ then $2b^2+2r^2+2-k=0\iff k=2b^2+2r^2+2\iff a=2b^3+2br^2+2b+r$ We get that $r$ is odd. \[4b^4+4b^2r^2+4b^2+2br+1|(2b^3+2br^2+b+r)^2\]\[4b^4+4b^2r^2+4b^2+2br+1|4b^6+4b^2r^4+b^2+r^2+8b^4r^2+4b^4+4b^3r+4b^2r^2+4br^3+2br\]Also \[4b^4+4b^2r^2+4b^2+2br+1|4b^6+4b^4r^2+4b^4+2b^3r+b^2\]$\implies 4b^4+4b^2r^2+4b^2+2br+1|4b^2r^4+r^2+4b^4r^2+2b^3r+4b^2r^2+4br^3+2br$ $4b^4+4b^2r^2+4b^2+2br+1|4b^4r^2+4b^2r^4+4b^2r^2+2br^3+r^2$ $\implies 4b^4+4b^2r^2+4b^2+2br+1|2b^3r+2br^3+2br$ $(4b^4+4b^2r^2+4b^2+2br+1,2b)=1$ so \[4b^4+4b^2r^2+4b^2+2br+1|b^2r+r^3+r\]But $4b^4+4b^2r^2+4b^2+2br+1>b^2r+r^3+r>0$ which gives a contradiction.$\blacksquare$ \[2b^2k+2br+1|2b^2k^2+4brk+k\]???
07.03.2024 06:39
Suppose that $a,b$ are two (not necessarily odd) positive integers such that $2ab+1 \mid a^2 + b^2 + 1$ and $a\neq b$. Prove that $2ab+1$ is a perfect square.
08.03.2024 11:00
vincentwant wrote: Suppose that $a,b$ are two (not necessarily odd) positive integers such that $2ab+1 \mid a^2 + b^2 + 1$. Prove that $2ab+1$ is a perfect square. wrong,if a=b,2ab+1 is not a perfect square.
09.03.2024 03:55
ylmath123 wrote: vincentwant wrote: Suppose that $a,b$ are two (not necessarily odd) positive integers such that $2ab+1 \mid a^2 + b^2 + 1$. Prove that $2ab+1$ is a perfect square. wrong,if a=b,2ab+1 is not a perfect square. sorry, forgot about the a-b=0 case, this should be fixed
10.12.2024 19:08
I am unable to share the picture of my detailed solution so I am typing it idk latex let there exists a1,b for which a1+b is minimum,and ((a1)^2+b^2+1)/(2(a1)b+1)=k=integers such that k≥2,root of a^2-a(2kb)+b^2+1-k=0 are a1,a2 where a2>0 then we get that (a2)=2kb-(a1) which is integer now for minimality (a2)≥(a1)>b thus as (a1)(a2)=b^2+1-k so (a1)^2<(a1)^2+1-2 which is clearly impossible thus we get for any a,b k=1 or if a0,b0 is a solution where (a0)>(b0) and if we replace a0 with x for which ((a0)^2+(b0)^2+1)/(2(a0).b0+1)=k0 is unchanged then x is 0 because x can't be negative as the unchanged quantity (a0) is positive thus for that we get that (a0)+x=(a0)=2(k0)(b0),(a0)x=0=(b0)^2+1-k by vietas relation thus we get solutions (a,b) are {(2k(k^2+1),k),(k,2k(k^2+1)),(k,k) where k is any natural}
10.12.2024 19:12
Oo is it called vieta jumping idk I know only vietas relation in jee quadratic equation chapter btw soory idk latex and also I am unable to share pic pls anyone check I used imo p6 1988 trick here I solved that by taking hint of minimality so it's the same one