2ab+1 | a^2 + b^2 + 1

Art of Problem Solving

AoPS Online

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

High School Olympiads Regional, national, and international math olympiads

Regional, national, and international math olympiads

3 M G

BBookmark VNew Topic kLocked

No tags match your search

M

2ab+1 | a^2 + b^2 + 1

G H J

Reveal topic tags

number theory proposed

L

G H BBookmark kLocked kLocked NReply

Source: Iran 3rd round 2013 - Number Theory Exam - Problem 2

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

240 posts

#1 h Sep 11, 2013, 2:42 PM • 3 Y

Y by Adventure10, GeoKing, Spiritpalm

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)

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

455 posts

#2 h Sep 11, 2013, 3:05 PM • 3 Y

Y by Adventure10, Mango247, Sadigly

Vieta jumping kills it. There might exist less OP methods to solve it, though.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3212 posts

#3 h Sep 11, 2013, 3:19 PM • 5 Y

Y by tensor, SohamSchwarz119, XbenX, Adventure10, Mango247

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}$ .

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1520 posts

mathuz

#4 h Sep 14, 2013, 10:13 AM • 3 Y

Y by Adventure10, Mango247, and 1 other user

my solution is by Vieta Jumping too!

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

7 posts

lawsy

#5 h Sep 14, 2013, 1:42 PM • 3 Y

Y by Giovanni98, Adventure10, animath_314159

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)$ ).

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#6 h Sep 14, 2013, 4:24 PM • 2 Y

Y by Adventure10 and 1 other user

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3212 posts

#7 h Sep 15, 2013, 12:11 AM • 2 Y

Y by Adventure10, Mango247

$a,b$ is two odd positive integers ??

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#8 h Sep 15, 2013, 4:25 PM • 3 Y

Y by Adventure10, Mango247, and 1 other user

My solution takes care of all parity cases, if you just read it carefully.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

3212 posts

#9 h Sep 15, 2013, 4:28 PM • 2 Y

Y by Adventure10, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

15142 posts

#10 h Sep 15, 2013, 4:32 PM • 2 Y

Y by Adventure10 and 1 other user

Oh, please, read the above posts. I already dealt with this issue, proving that it cannot be negative.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

sayantanchakraborty

505 posts

sayantanchakraborty

#11 h Sep 6, 2014, 6:15 PM • 4 Y

Y by Kameawtamprooz, Adventure10, Mango247, Captainscrubz

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??

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1080 posts

#13 h Dec 30, 2021, 7:41 PM • 1 Y

Y by centslordm

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

cursed_tangent1434

604 posts

cursed_tangent1434

#14 h Dec 28, 2023, 1:07 AM • 1 Y

Y by GeoKing

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

713 posts

#15 h Mar 5, 2024, 8:55 PM

Y by

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.

P is at least 2
P=1
P=0

This post has been edited 3 times. Last edited by bin_sherlo, Mar 7, 2024, 6:13 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

2686 posts

Vulch

#16 h Mar 6, 2024, 9:23 AM

Y by

Redacted.

This post has been edited 3 times. Last edited by Vulch, Mar 6, 2024, 11:33 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1170 posts

#17 h Mar 6, 2024, 11:24 AM • 1 Y

Y by Vulch

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.$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

105 posts

#18 h Mar 7, 2024, 1:09 AM

Y by

$2b^2k+2br+1|2b^2k^2+4brk+k$ ？？？

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

105 posts

#20 h Mar 7, 2024, 1:16 AM

Y by

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$ ？？？

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1354 posts

#21 h Mar 7, 2024, 3:39 AM

Y by

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.

This post has been edited 2 times. Last edited by vincentwant, Mar 9, 2024, 12:55 AM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

105 posts

#22 h Mar 8, 2024, 8:00 AM

Y by

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

1354 posts

#23 h Mar 9, 2024, 12:55 AM

Y by

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Nobitasolvesproblems1979

25 posts

Nobitasolvesproblems1979

#28 h Dec 10, 2024, 4:08 PM • 1 Y

Y by GeoKing

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}

This post has been edited 1 time. Last edited by Nobitasolvesproblems1979, Dec 17, 2024, 10:24 PM
Reason: Typing error

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Nobitasolvesproblems1979

25 posts

Nobitasolvesproblems1979

#29 h Dec 10, 2024, 4:12 PM • 1 Y

Y by GeoKing

Oo is it called vieta jumping idk I know only vietas relation in jee quadratic equation chapter :blush:

:blush:

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

4 posts

#30 h Apr 13, 2025, 11:23 PM

Y by

Let a²+b²+1/2ab+1 =k.
a²+b²-2ab+1-k=0
Let assume that (a0,b0) is a solution of above equation such that a0≠b0,a0>b0,a0+b0 is minimum and a0,b0 are odd a²+(b0)²-2a(b0)+1-k=0
The above equation has a0 has one of its roots and a1(let).
a0+a1=2(b0)k.It implies that a1 is also odd.
a0a1=(b0)²+1-k a1=((b0)²+1-k)/a0
Due to minimality of a0, a0<a1 (a0)²<(b0)²+1-k
k-1<(b0-a0)(b0+a0)
(a0-b0)²)/2(a0)(b0)+1 < (b0-a0)(b0+a0)
(a0-b0)/2(a0)(b0)+1 < -(a0+b0)
This is a contradiction.
It implies that a0 is not minimum
By FMID,we can say that if 2ab+1|a²+b²+1 then a=b. (a0 means that 0 is in subscript of a).This is my first post so don't know how to post a good written solution.

This post has been edited 1 time. Last edited by Pseudo_Matter, Apr 13, 2025, 11:27 PM
Reason: The previous post was messy

Z K Y

N Quick Reply

G

H

=

© 2025 AoPS Incorporated

a