Suppose that a,b are two odd positive integers such that 2ab+1∣a2+b2+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∣a2+b2+1. Prove that a=b. (15 points) Let a2+b2+12ab+1=k with k∈N∗. Hence a2+b2−2abk+1−k=0(1). Let (a0,b0) be the root such that a0+b0 is minimum. Without loss of generality, assume that a0≤b0. Considering the equation x2−2a0k⋅x+a20−k+1=0 It follows that b0 is a solution of the equation. Let b1 be the other solution. Since (a0,b1) is also a root of the equation (1) then a0+b0≤a0+b1 implies b0≤b1. By Vieta theorem we have {b0+b1=2a0kb0⋅b1=a20−k+1. ▸ 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=0will 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+1which implies that, a\geq 2b^3+2b and since a is odd, we have that, a>2b^3+2bNow, 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>awhich 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-4br2b^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 0is 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-4br2b^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)^24b^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+2brAlso 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+rBut 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