Russian NT with a Ceiling

The post below has been deleted. Click to close.

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

naman12

1358 posts

naman12

#1 h Sep 22, 2020, 11:28 PM • 8 Y

Y by pavel kozlov, magicarrow, benthegreatest, skyscraper, megarnie, Inconsistent, Hoto_Mukai, NO_SQUARES

Let $a$ and $b$ be two positive integers. Prove that the integer
$a^2+\left\lceil\frac{4a^2}b\right\rceil$ is not a square. (Here $\lceil z\rceil$ denotes the least integer greater than or equal to $z$ .)

Russia

This post has been edited 2 times. Last edited by naman12, Sep 22, 2020, 11:29 PM

Z K Y

The post below has been deleted. Click to close.

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

v_Enhance

6877 posts

v_Enhance

#2 h Sep 22, 2020, 11:29 PM • 23 Y

Y by Pal702004, pavel kozlov, rf20008, magicarrow, benthegreatest, iman007, v4913, alinazarboland, HamstPan38825, mathleticguyyy, math31415926535, nguyennam_2020, hsiangshen, Inconsistent, rayfish, DaRKst0Rm, Kingsbane2139, sabkx, TheHimMan, bhan2025, ihategeo_1969, ehuseyinyigit, Sedro

Assume not. It is equivalent to $a^2 + \frac{4a^2+e}{b} = c^2$ for some $0 \le e < b$ . Write this as $(b+4)a^2 - bc^2 = -e.$ At face, this is a cool assertion that a large family of Pell-like equations has no solutions. However it turns out we can Vieta jump by letting $c = \frac{x+y}{2}$ and $a = \frac{x-y}{2}$ (since $c > a$ ), which rewrites the equation as $x^2 - (b+2)xy + y^2 = -e.$ Then given $x \ge y \ge 1$ we have a Vieta jump $(x,y) \longmapsto \left( y, \frac{y^2+e}{x} \right) = \left( y, (b+2)y-x \right).$ To complete the descent argument, we need to check:
Claim: For $xy \ge 2$ , we always have $0 < \frac{y^2+e}{x} < x$ .
Proof. The left inequality is obvious. For right inequality, the given equation is $(x-y)^2 - bxy = -e > -b \implies (x-y)^2 > bxy-b \ge b$ and thus $x^2-y^2 = (x-y)(x+y) > (x-y)^2 > b > e$ which implies the desired result. $\blacksquare$
Therefore, the Vieta jumping can only conclude when $(x,y) = (1,1)$ . However, plugging this back into the initial equation gives $2-(b+2) = -e$ or $b=e$ , which doesn't work.

Z K Y

The post below has been deleted. Click to close.

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

HKIS200543

380 posts

HKIS200543

#3 h Sep 23, 2020, 12:10 AM • 7 Y

Y by pavel kozlov, MihaiT, Ninjasolver0201, benthegreatest, samrocksnature, Kingsbane2139, NO_SQUARES

A very long solution using continued fractions:

We try to bound
$\left\lfloor a \sqrt{1 + 4/b} \right\rfloor^2 < a^2 + \left\lceil \frac{4a^2}{b} \right\rceil < \left\lceil a \sqrt{1 + 4/b} \right\rceil^2 .$ Since $a \sqrt{1+4/b}$ is obviously not an integer, this solves the problem. The lower bound is immediate from
$\left\lfloor{a \sqrt{1+4/b}}\right\rfloor^2 < (a \sqrt{1 + 4/b})^2 \leq a^2 + \left\lceil{\frac{4a^2}{b}}\right\rceil .$ The upper bound is the difficult part. Let $\delta = \left\lceil{a \sqrt{1 + 4/b}}\right\rceil - a\sqrt{1 + 4/b}$ . Then
$\left\lceil{a \sqrt{1+ 4/b}}\right\rceil^2 = a^2 + \frac{4a^2}{b} + 2\delta a \sqrt{1 + 4/b} + \delta^2. \tag{$\dagger$}$ If $b$ divides $4a^2$ , then the bound is immediate since $\left\lceil{\frac{4a^2}{b}} \right\rceil = \frac{4a^2}{b}$ . Otherwise, it suffices to prove that
$\delta \geq \frac{1}{2a} \iff \{ a\sqrt{1 + 4/b} \} \leq 1 - \frac{1}{2a} .$ This is where we devote most of our efforts to.

Now we show that there are no solutions when $b \geq 5$ . First, observe that if $b \in \{1,2,4 \}$ , then $b \mid 4a^2$ , so there are no solutions. Moreover if $b = 3$ and $3 \mid a$ there are no solutions, too. Otherwise $4a^2 \equiv 1 \pmod{3}$ . Thus the expression is equal to a perfect square $c^2$ if and only if
$3c^2 - 7a^2 = 2.$ However, by taking both sides (mod 4), this is impossible. Henceforth, assume that $b \geq 5$ . We shall use extensively various facts about continued fractions and diophantine approximations.

Claim. Let $\lambda = \frac{1}{2}({\sqrt{1 + 4/b}} - 1)$ . Then
$\lambda = [0, b, 1, b, 1, \dots ],$ using the standard notation for simple continued fractions.
Proof. It is well known that
$\sqrt{x} = 1 + \dfrac{x-1}{2 + \frac{x-1}{2 + \frac{x-1}{2+ \cdots}}}.$ Inputting $x = {1 + b/4}$ , we obtain
$\begin{align*} \sqrt{1 + 4/b} &= 1 + \frac{4/b}{2 + \frac{4/b}{2 + \frac{4/b}{2 + \frac{4/b}{ 2 + \cdots}}}} \\ &= 1 + \frac{4}{2b + \frac{4}{2 + \frac{4}{2b + \frac{4}{2+ \cdots}}}} \\ &= 1 + \frac{2}{b + \frac{1}{1 + \frac{1}{b + \frac{1}{1 + \cdots}}}}. \end{align*}$ The claim follows immediately.

Then
$\{ a \sqrt{1 + 4/b} \} = \{ 2a \lambda \}.$ This is what we will bound. Consider the sequence of convergents $(p_n/q_n)$ that come from the continued fraction of $\lambda$ . We use three well known facts about the convergents for a simple continued fraction $[a_0, a_1, a_2, \dots ]$ .

If $n$ is odd, then $p_n/q_n$ is greater than $\lambda$ . If $n$ is even, then $p_n/ q_n$ is less than $\lambda$ .
For each $n \geq 2$ ,
$q_n = a_n q_{n-1} + q_{n-2} = \begin{cases} q_{n-1} + q_{n-2} &\text{if $n$ is even,} \\ bq_{n-1} + q_{n-2} &\text{if $n$ is odd.} \end{cases} \tag{1}$ As a corollary of this, we have that the sequence $(q_n)$ is strictly increasing. Moreover, because $q_1 = b$ , we also have that $b$ divides $q_n$ whenever $n$ is odd by induction.
For each $n$ ,
$\left| { \lambda - \frac{p_n}{q_n}} \right| < \frac{1}{q_n q_{n+1}} . \tag{2}$
For each $n$ ,
$p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1}. \tag{3}$

Let $n$ be the greatest index such that $q_n \leq 2a < q_{n+1}$ . Let $\varepsilon = | \lambda - p_n / q_n |$ and $\hat{a} = 2ap_n \pmod{q_n}$ . It follows that
$\{ 2a \lambda \} = \left\{ \frac{\hat{a}}{q_n} \pm 2a \varepsilon \right\},$ with the sign $\pm$ depending on the parity of $n$ . By (2), we have that
$2a \varepsilon < \frac{2a}{q_n q_{n+1}} < \frac{1}{q_n}.$ This gives us almost everything we need. From here, we split into cases based on the parity of $n$ .

Case 1.If $n$ is odd, then as long as $\hat{a} \neq 0$ , then
$0 < \{ 2a \lambda \} < \frac{q_n-1}{q_n} < 1 - \frac{1}{2a}.$ Thus the only problem is if $q_n \mid 2a$ (bearing in mind that $\gcd(p_n, q_n) = 1$ ). However, by assumption $b$ does not divide $2a$ , so this is impossible since $b$ divides $a_n$ .

Case 2. If $n$ is even, then we have
$\{2a \lambda \} < \frac{q_n-2}{q_n} + \frac{1}{q_n} < 1 - \frac{1}{2a}$ unless $\hat{a} = q_n - 1$ .

Thus we just have to deal with this edge case. First, we will deal with if $2a > q_{n+1} - 1.5q_n$ .Then we will prove that
$\frac{1}{x} + \frac{x}{q_n q_{n+1}} < \frac{1}{q_n} \tag{4}$ for all $x \in [q_n, q_{n+1} - 1.5q_n]$ . Taking $x = 2a$ , this would imply that
$\{ 2a \lambda \} < 1 - \frac{1}{q_n} + \frac{2a}{q_nq_{n+1}} < 1 - \frac{1}{2a}.$
Suppose that $2a > q_{n+1} - 1.5q_n$ . Because $2a$ is very close to $q_{n+1}$ , we may use $\frac{p_{n+1}}{q_{n+1}}$ as a very good diophantine approximation. More precisely, we have
$\{ 2a \lambda\} < 1 - \frac{1}{q_{n+1}} - \frac{2a}{q_{n+`1} q_{n+2}}$ Thus it is sufficient to prove that
$\frac{1}{2a} - \frac{2a}{q_{n+1} q_{n+2}} < \frac{1}{q_{n+1}}$ From here, we invoke a number of bounds.

By applying (1), we obtain that $q_{n} < \frac{1}{b} q_{n+1}$ . Thus $2a \geq q_n( 1 - \frac{3}{2b})$
Again from (1), we have that $q_{n+2} < 2q_{n+1}$ .

Thus
$\frac{1}{2a} - \frac{2a}{q_{n+1} q_{n+2}} < \frac{1}{q_n(1 - \frac{3}{2b})} - \frac{q_{n+1}}{2q_{n+1}^2} = \frac{1}{q_{n+1}} \left( \frac{2b}{2b-3} - \frac{1}{2} \right)$ For $b \geq 5$ , we have $\frac{2b}{2b-3} - \frac{1}{2} < 1$ , so we are done.

Now we just have to do some analysis to prove the bound in (4). Let $f(x) = \frac{1}{x} + \frac{x}{q_nq_{n+1}}$ . Then $f'(x) = \frac{1}{q_nq_{n+1}} - \frac{1}{x^2}$ . Hence $f'$ changes sign just once on $[q_n, q_{n+1} - 1.5 q_n]$ .

Our strategy is to find prove that $f(q_{n+1} - 1.5 q_n) < \frac{1}{q_n}$ and to find $\alpha \leq 2a$ such that $f( \alpha) < \frac{1}{q_n}$ . Because $f'$ changes sign just once, this is enough to imply the inequality in $(4)$ .

The bound for $f(q_{n+1} - 1.5 q_n)$ is just a computaiton:
$f(q_{n+1} - 1.5 q_n) = \frac1{q_{n+1} - 1.5 q_n} + \frac{1}{q_n} - \frac{3}{2q_{n+1}} .$ Using that $q_n < \frac{1}{b} q_{n+1}$ we may bound
$\frac{1}{q_{n+1} - 1.5 q_n} < \frac{1}{q_{n+1}(1 - \frac{3}{2b})} < \frac{3}{2} q_{n+1}$ with the final inequality holding for $b \geq 5$ . This establishes $f(q_{n+1} - 1.5 q_n) < \frac{1}{q_n}$ .

I claim we can take $\alpha = \frac{3}{2} q_n$ . By (3),
$2a \equiv q_{n+1} \pmod{q_n}$ But
$q_{n+1} \pmod{q_n} = q_{n-1} > \frac{q_n}{2}$ by (1). Thus $2a \geq \frac{3}{2} q_n$ . Again, we check that
$f \left( \frac{3}{2} q_n \right) = \frac{2}{3q_n} + \frac{3}{2q_{n+1}} < \left( \frac{2}{3} + \frac{3}{2b} \right) \frac{1}{q_n} < \frac{1}{q_n}.$ This concludes the proof.

This post has been edited 2 times. Last edited by HKIS200543, Sep 23, 2020, 1:05 AM

Z K Y

The post below has been deleted. Click to close.

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

a1267ab

223 posts

a1267ab

#4 h Sep 23, 2020, 3:12 AM

Y by

PEN A4

nnosipov wrote:

If $a$ , $b$ , $c$ are positive integers such that
$|a^2+b^2-abc-2|<c,$ then $a^2+b^2-abc$ is 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.

pavel kozlov

616 posts

pavel kozlov

#5 h Sep 23, 2020, 6:20 AM • 20 Y

Y by Imayormaynotknowcalculus, khina, Aryan-23, v_Enhance, 62861, Bumblebee60, WolfusA, FaithnHope, Aimingformygoal, tigerzhang, Inconsistent, Wizard0001, Quidditch, sabkx, Kingsbane2139, starchan, NO_SQUARES, MELSSATIMOV40, Sedro, ehuseyinyigit

v_Enhance wrote:

At face, this is a cool assertion that a large family of Pell-like equations has no solutions.

(Proposed by me

).Yes, one could use this old classical idea which was hidden in the new frames. But I think there are many different approaches.

Z K Y

The post below has been deleted. Click to close.

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

Idio-logy

206 posts

Idio-logy

#6 h Sep 23, 2020, 6:23 AM • 2 Y

Y by Nathanisme, Mango247

The same substitution also appeared in Shortlist 2016 N5.

Z K Y

The post below has been deleted. Click to close.

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

MarkBcc168

1595 posts

MarkBcc168

#7 h Sep 23, 2020, 6:28 AM • 1 Y

Y by pavel kozlov

Comment: This is a neat problem. However, the trick of multiplying units to descent is somewhat known. Had I thought about this during the TST, I would have solved it easily.

Replace $b$ with $k$ . First, we reduce the equation to a general Pell's equation.

Claim: The equation implies $k(k+4)x^2-y^2 \in\{0,4,8,\hdots,4k-4\}$ for some $x,y\in\mathbb{Z}^+$

Proof. Set $4a^2\equiv -r\pmod k$ where $r\in\{0,1,\hdots,k-1\}$ . Then we have (for some $b\in\mathbb{Z}$ ) that
$ka^2 + (4a^2+r) = kb^2 \implies kb^2 - (k+4)a^2 = r.$ Motivated by the identity
$(\sqrt{k+4}-\sqrt{k})(b\sqrt{k}-a\sqrt{k+4}) = -(a(k+4)+bk)+(a+b)\sqrt{k(k+4)},$ we set $x = a+b$ and $y=a(k+4)+bk$ ; a straightforward algebra yields the claim. $\blacksquare$

Now we do the descent. Consider the solution with $x$ as small as possible. Multiplying by $\sqrt{k(k+4)}-k$ , we get the miraculous identity
$k(k+4)\left(y-(k+2)x\right)^2 - \left(k(k+4)x - (k+2)y\right)^2 = 4\left(k(k+4)x^2 - y^2\right).$ Thus, we have the solution (a straightforward parity check gives that these are indeed integers)
$\left(\frac{y-(k+2)x}{2}, \frac{k(k+4)x - (k+2)y}{2}\right).$ By minimality, we have
$\frac{y-(k+2)x}{2} \notin (-x,x) \iff y \notin (kx, (k+4)x)$ so we split into two cases.

If $y\leq kx$ , then $k(k+4)x^2 - y^2 \geq 4kx^2\geq 4k$ , contradiction.
If $y\geq (k+4)x$ , then $k(k+4)x^2 - y^2 \leq k(k+4)x^2 - (k+4)^2x^2 < 0$ , contradiction.

Hence, we are done by infinite descent.

This post has been edited 2 times. Last edited by MarkBcc168, Nov 4, 2020, 2:28 AM

Z K Y

The post below has been deleted. Click to close.

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

fukano_2

492 posts

fukano_2

#8 h Sep 23, 2020, 9:10 AM

Y by

redacted

This post has been edited 8 times. Last edited by fukano_2, Oct 27, 2021, 10:33 AM

Z K Y

The post below has been deleted. Click to close.

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

62861

3564 posts

62861

#9 h Sep 23, 2020, 11:41 AM • 23 Y

Y by Aryan-23, MihaiT, mijail, mira74, Gaussian_cyber, magicarrow, fjm30, math90, zephyr7723, srijonrick, Modesti, Atpar, 596066, aopsuser305, Assassino9931, jrsbr, gvole, Kingsbane2139, Zsigmondy, Supercali, khina, ngduchieu1903, ehuseyinyigit

Recall that ELMO 2012 SL N6 states that for any positive integers $x$ , $y$ with $(x, y) \ne (1, 1)$ , we have
$\left\lfloor\frac{(x-y)^2-1}{xy}\right\rfloor=\left\lfloor\frac{(x-y)^2-1}{xy-1}\right\rfloor.$ Now return to the original problem. Suppose that the expression equals $(a+k)^2$ , with $k > 0$ . Apply the ELMO SL problem to $(k, 2a+k)$ to obtain that
$\begin{align*} \left \lfloor \frac{4a^2 - 1}{2ak + k^2} \right \rfloor & = \left \lfloor \frac{4a^2 - 1}{2ak + k^2 - 1} \right \rfloor\\ \iff \left \lceil \frac{4a^2}{2ak + k^2} \right \rceil & = \left \lceil \frac{4a^2}{2ak + k^2 - 1} \right \rceil. \end{align*}$ However, $a^2 + \left \lceil \tfrac{4a^2}{b} \right \rceil = (a + k)^2$ implies
$\frac{4a^2}{2ak + k^2} \le b < \frac{4a^2}{2ak + k^2 - 1},$ contradiction.

Z K Y

The post below has been deleted. Click to close.

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

pavel kozlov

616 posts

pavel kozlov

#12 h Sep 23, 2020, 12:47 PM • 4 Y

Y by uvuvwevwevwe, Msn05, Kingsbane2139, Mango247

CantonMathGuy wrote:

Recall that ELMO 2012 SL N6 states that for any positive integers $x$ , $y$ with $(x, y) \ne (1, 1)$ , we have
$\left\lfloor\frac{(x-y)^2-1}{xy}\right\rfloor=\left\lfloor\frac{(x-y)^2-1}{xy-1}\right\rfloor.$ Now return to the original problem. Suppose that the expression equals $(a+k)^2$ , with $k > 0$ . Apply the ELMO SL problem to $(k, 2a+k)$ to obtain that
$\begin{align*} \left \lfloor \frac{4a^2 - 1}{2ak + k^2} \right \rfloor & = \left \lfloor \frac{4a^2 - 1}{2ak + k^2 - 1} \right \rfloor\\ \iff \left \lceil \frac{4a^2}{2ak + k^2} \right \rceil & = \left \lceil \frac{4a^2}{2ak + k^2 - 1} \right \rceil. \end{align*}$ However, $a^2 + \left \lceil \tfrac{4a^2}{b} \right \rceil = (a + k)^2$ implies
$\frac{4a^2}{2ak + k^2} \le b < \frac{4a^2}{2ak + k^2 - 1},$ contradiction.

Wow, what a trick

Z K Y

The post below has been deleted. Click to close.

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

MihaiT

750 posts

MihaiT

#13 h Sep 23, 2020, 12:54 PM

Y by

indeed nice!

Z K Y

The post below has been deleted. Click to close.

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

Hamel

392 posts

Hamel

#14 h Sep 24, 2020, 11:52 AM • 1 Y

Y by gvole

This was Greek TST Problem 4

Z K Y

The post below has been deleted. Click to close.

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

meql

20 posts

meql

#15 h Sep 24, 2020, 1:33 PM • 3 Y

Y by magicarrow, Modesti, Tellocan

I prove the stronger statement that $a^2+4\left\lceil\frac{a^2}{b}\right\rceil$ is not square. (This is stronger because replacing $a$ with $2a$ gives the original problem times 4.) I will use induction on $a$ . If $a=1$ , the sum is always 5, so we are done. Now assume it is true for $1,2,\cdots a-1$ , and assume $a^2+4\left\lceil\frac{a^2}{b}\right\rceil=(a+d)^2$ for some $d$ . Notice that $d$ must be even, so let $d=2k$ . Then we have $\left\lceil\frac{a^2}{b}\right\rceil=ak+k^2$ . Now notice that
$a^2-k^2<a^2\implies \frac{a-k}{k}<\frac{a^2}{k(a+k)}$ and
$ak\leq ak+k^2-1 \implies \frac{a^2}{ak+k^2-1}\leq \frac{a}{k}$ Thus, since $ak+k^2-1<\frac{a^2}{b}\leq ak+k^2$ , we have
$\frac{a}{k}-1<\frac{a^2}{ak+k^2}\leq b<\frac{a^2}{ak+k^2-1}\leq \frac{a}{k}$ Let $a=nk+r$ for some $0\leq r\leq k-1$ . If $n=0$ , then $\left\lceil\frac{a^2}{b}\right\rceil\leq r^2<rk+k^2$ , which is a contradiction. If $r=0$ , then both $\frac{a}{k}-1$ and $\frac{a}{k}$ are integers, contradicting the above inequality. But then $n-1+\frac{r}{k}<b<n+\frac{r}{k}$ , so $b=n$ . Thus, we have
$\left\lceil\frac{a^2}{b}\right\rceil=\left\lceil\frac{n^2k^2+2nkr+r^2}{n}\right\rceil=nk^2+2kr+\left\lceil\frac{r^2}{n}\right\rceil$ And since $ak+k^2=k^2+nk^2+kr$ , we get $k^2=kr+\left\lceil\frac{r^2}{n}\right\rceil$ . Thus, $r^2+4\left\lceil\frac{r^2}{n}\right\rceil=r^2+4(k^2-kr)=(2k-r)^2$ . But from induction, since $r<k<a$ , $r^2+4\left\lceil\frac{r^2}{n}\right\rceil$ is not a square, so this is a contradiction. Thus, $a^2+4\left\lceil\frac{a^2}{b}\right\rceil$ is never a square.

Z K Y

The post below has been deleted. Click to close.

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

ProblemSolver2048

104 posts

ProblemSolver2048

#16 h Sep 24, 2020, 2:37 PM

Y by

Replace b with k well then we reduce it to a general Pells equation
Claim: The equation implies $k(k+4)x^2-y^2 \in\{0,4,8,\hdots,4k-4\}$ for some x,y is an element of Z^+
Proof: Set 4a^2 is congruent -r(mod k) where r is an element of {0,1....,k-1}. Then we have (for some b is an element of Z) that ka^2+(4a^2+r)=kb^2, kb^2-(k+4)a^2=r
Motivated by the identity
(sqrtk+4-sqrtk)(bsqrtk-asqrtk+4)=-(a(k+4)+bk+(a+b)sqrtk(k+4),
we can now set to x=a+b and y=a(k+4)+bk which is straightforward algebra which yields the claim. $\blacksquare$
Consider the solution with x as small as possible multiplying by sqrtk(k+4)-k we get the miraculous identity
k(k+4) (y-(k+2)x^2-(k(k+4)x-(k+2)y^2=4(k(k+4)x^2-y^2).
Thus we have a solution that is (a straightforward parity check gives that these are indeed integers)
y-k(+2)x/2 isn't an element (-x,x) which is y is not an element of (kx,(k+4)x)
so we split into two cases
If y<=kx then k(k+4)x^2-y^2>=4kx^2>=4k, contradiction.
If y>=(k+4)x, then k(k+4)x^2-y^2<=k(k+4)x^2-(k+4)x^2x^2<0 which is a contradiction.
Hence it is a contradiction :starwars:

Note : I would personally do Evan Chens solution well related to his it is the vieta jumping one which is pretty clean ig this was a good ISL I guess :starwars.

Credits to Markbcc186 or acknowledgements to him. I didn't write this up.

This post has been edited 1 time. Last edited by ProblemSolver2048, Dec 14, 2020, 7:35 PM

Z K Y

The post below has been deleted. Click to close.

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

math90

1477 posts

math90

#17 h Sep 24, 2020, 6:38 PM • 4 Y

Y by pavel kozlov, Mango247, Mango247, Mango247

Posting for storage.

Assume there exists a positive integer $c$ such that
$a^2+\left\lceil\frac{4a^2}b\right\rceil=c^2$ Hence
$\left\lceil\frac{4a^2}b\right\rceil=c^2-a^2=(c+a)(c-a)$ Let $c+a=x$ and $c-a=y$ . Hence
$\frac{(x-y)^2+r}b=xy$ with $0\le r<b$ . Of course $x\ne y$ so assume $x>y$ . Moreover assume $x+y$ is minimal. The equation may be written as
$x^2-(b+2)xy+y^2+r=0$ Observe that if $(x,y)$ is a solution to the equation then $\left((b+2)y-x,y\right)$ is also a solution. Hence it suffices to prove that
$(b+1)y<x<(b+2)y$ to obtain a contradiction. It is true since
$0>y^2-(b+2)xy=y\left[x-(b+2)y\right]$ and
$0<x^2-(b+2)xy+y^2+b=(x-y)^2+b(1-xy)\le (x-y)^2+b(y^2-xy)=(x-y)(x-y-by)=(x-y)\left[x-(b+1)y\right]$

Z K Y

The post below has been deleted. Click to close.

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

TechnoLenzer

55 posts

TechnoLenzer

#34 h May 10, 2022, 6:55 PM • 1 Y

Y by pavel kozlov

Assume $(a+n)^2 = a^2 + \left\lceil\frac{4a^2}b\right\rceil$ .

Part 1: Conversion into algebra

$\begin{align*} &\iff 2an + n^2 = \left\lceil\frac{4a^2}b\right\rceil \\ &\iff 2an + n^2 \geq \frac{4a^2}b> 2an + n^2 - 1 \\ &\iff \frac{4a^2}{2an + n^2 - 1} > b \ge \frac{4a^2}{2an + n^2}. \tag{1} \\ \end{align*}$
Claim 2: $\frac{4a^2}{2an + n^2} = \frac{2a}{n} - \frac{2a}{2a + n}$ .

Proof:
$\begin{align*} \frac{2a}{n} - \frac{2a}{2a + n} &= \frac{4a^2 + 2an}{n(2a+n)} - \frac{2an}{n(2a+n)} \\ &= \frac{4a^2 + 2an - 2an}{n(2a + n)} = \frac{4a^2}{2an + n^2}. \quad \square \\ \end{align*}$
Claim 3: $\frac{4a^2}{2an + n^2 - 1} = \frac{2a}{n} - \frac{2a}{n} \left( \frac{n^2 - 1}{2an + n^2 - 1} \right)$ .

Proof:
$\begin{align*} \frac{2a}{n} \left (1 - \frac{n^2 - 1}{2an + n^2 - 1} \right) &= \frac{2a}{n} \left( \frac{2an + (n^2 - 1) - (n^2 - 1)}{2an + n^2 - 1} \right) \\ &= \frac{2a}{n} \left( \frac{2an}{2an + n^2 - 1} \right) = \frac{4a^2}{2an + n^2 - 1}. \quad \square \\ \end{align*}$
Claim 4: $n \le 2a$ .

Proof: $\left\lceil\frac{4a^2}b\right\rceil \le 4a^2$ for $b \in \mathbb{N}$ . Hence, $(a+n)^2 = a^2 + \left\lceil\frac{4a^2}b\right\rceil \le 5a^2 \le 9a^2 \Rightarrow a + n \le 3a \Rightarrow n \le 2a$ . $\square$

Let $d = 2a$ . By $(1)$ and Claims 2, 3,
$\begin{align*} \frac{d}{n} - \frac{d}{n}\left( \frac{n^2 - 1}{dn + n^2 - 1} \right) > b \ge \frac{d}{n} - \frac{d}{d+n} \tag{5} \end{align*}$
By Claim 4, we can let $d = kn - c$ , for $k \in \mathbb{N} \ge 2$ , $0 \le c < n$ .

Now $(5)$ becomes:
$\begin{align*} k - \frac{c}{n} - \frac{kn - c}{n} \left( \frac{n^2 - 1}{kn^2 - cn + n^2 - 1} \right) &> b \ge k - \frac{c}{n} - \frac{kn-c}{(k+1)n - c} \\ \Rightarrow - \frac{c}{n} - \frac{kn - c}{n} \left( \frac{n^2 - 1}{kn^2 - cn + n^2 - 1} \right) &> b - k \ge - \frac{c}{n} - \frac{kn-c}{(k+1)n - c} \tag{6} \end{align*}$
$0 \le c < n \Rightarrow 0 \le \frac{c}{n} < 1$ , and furthermore $kn-c < (k+1)n-c$ so $0 \le \frac{kn-c}{(k+1)n-c} < 1$ . Thus, $-2 < RHS \le 0$ .

Similarly, $n^2 \ge 1 \Rightarrow \frac{n^2 - 1}{kn^2 - cn + n^2 - 1} \ge 0$ . Thus, $LHS \le 0$ , but $LHS > RHS$ so $LHS > -2$ as well.

Part 2: Fixing bounds between integers

Now, it suffices to show that
$\begin{align*} \frac{kn-c}{n} \left( \frac{n^2 - 1}{(k+1)n^2 - cn - 1} \right) - \frac{n-c}{n}&\ge 0 \tag{7} \\ \iff \frac{kn-c}{(k+1)n - c} - \frac{n-c}n &\ge 0 \tag{8} \end{align*}$ and that neither expression equals zero, for $n \in \mathbb{Z}$ , $0 \le c < n$ , because this implies

$\begin{align*} - \frac{c}{n} - \frac{kn - c}{n} \left( \frac{n^2 - 1}{(k+1)n^2 -cn - 1} \right) &\le -1 \\ \iff - \frac{kn - c}{n} \left( \frac{n^2 - 1}{(k+1)n^2 -cn - 1} \right) &\le - \frac{n-c}{n} \\ \iff \frac{kn - c}{n} \left( \frac{n^2 - 1}{(k+1)n^2 -cn - 1} \right) &\ge \frac{n-c}{n} \\ \iff \frac{kn-c}{(k+1)n - c} - \frac{n-c}n &\ge 0 \\ \iff - \frac{kn-c}{(k+1)n - c} &\le - \frac{n-c}n \\ \iff - \frac{c}{n} - \frac{kn-c}{(k+1)n - c} &\le -1 \end{align*}$ so both bounds always lie within either $(-2, -1)$ or $[-1, 0]$ , and hence $b-k$ does too. However, note that $0 \ge LHS > b-k$ , so $b-k \neq 0$ . Furthermore, if either bound is -1, (7) or (8) must be equality, which contradicts our claim. Thus, $b-k$ ends up in $(-2, -1)$ or $(-1, 0)$ , so cannot be an integer. But $b-k \in \mathbb{Z} \iff b \in \mathbb{Z}$ since $k$ integer, so $b \not \in \mathbb{Z}$ , which is a contradiction.

Part 3: Proof of equivalence

$\begin{align*} (7) \iff (kn-c)(n^2-1) - (n-c)((k+1)n^2 - cn - 1) &\ge 0 \\ \iff kn^3 - cn^2 - kn + c - (k+1)n^3 + c(k+1)n^2 + cn^2 - c^2n + n - c &\ge 0 \\ \iff -kn - n^3 + c(k+1)n^2 - c^2n + n &\ge 0 \\ \iff -n^2 + c(k+1)n + (1 - k - c^2) &\ge 0. \tag{9} \end{align*}$
$\begin{align*} (8) \iff n(kn-c) - ((k+1)n - c)(n-c) &\ge 0 \\ \iff kn^2 - cn - (k+1)n^2 + c(k+1)n + cn - c^2 &\ge 0 \\ \iff -n^2 + c(k+1)n - c^2 &\ge 0. \tag{10} \end{align*}$
$\begin{align*} (9) \iff n &\in \left [ \frac{-c(k+1) + \sqrt{c^2(k+1)^2 + 4(c^2 + k - 1)}}{-2}, \frac{-c(k+1) - \sqrt{c^2(k+1)^2 + 4(c^2 + k - 1)}}{-2} \right] \\ \iff n &\in \left [ \frac{c}{2} \left((k+1) - \sqrt{(k+1)^2 + 4\left (1 + \frac{k-1}{c^2} \right)} \right), \frac{c}{2} \left((k+1) + \sqrt{(k+1)^2 + 4(1 + \frac{k-1}{c^2})} \right) \right]. \end{align*}$ Note that the lower bound $< \frac{c}{2} ((k+1) - \sqrt{(k+1)^2}) = 0$ , so

$(9) \iff n \le \frac{c}{2} \left((k+1) + \sqrt{(k+1)^2 + 4(1 + \frac{k-1}{c^2})} \right)$ .

Similarly, $(10) \iff n \le \frac{c}{2} ((k+1) + \sqrt{(k+1)^2 + 4})$ , but because $k \ge 2$ , all differences of two squares are $\ge 7$ , and hence $(k+1)^2 + 4 < (k+2)^2$ . Thus, $(10) \iff n \le \frac{c}{2} ((k+1) + (k+1)) = c(k+1)$ .

Now
$\begin{align*} n &> c(k+1) \\ \Rightarrow (k+1)^2 + 4\left (1 + \frac{k-1}{c^2} \right) &\ge (k+3)^2 \\ \Rightarrow 4 + 4 \cdot \frac{k-1}{c^2} &\ge 4k + 8 \\ \Rightarrow \frac{k-1}{c^2} &\ge k + 1 \tag{11} \end{align*}$ If $c = 0$ , (9) and (10) both yield $-n^2 \ge 0$ , a contradiction as $n \in \mathbb{Z}$ .

If $c \ge 1$ , (11) is false.

Part 4: Proof that equality is impossible

For (10), as above, $(k+1)^2 < (k+1)^2 + 4 < (k+2)^2$ and so $\sqrt{(k+1)^2 + 4}$ isn't an integer, and $n$ isn't either. Contradiction.

For (11), if $c = 0$ , $n = 0$ , contradiction. If $c = 1$ , $(k+1)^2 < (k+1)^2 + 4k < (k+3)^2$ , so $(k+1)^2 + 4k = (k+2)^2 \Rightarrow 2k = 3$ , also contradiction. If $c \ge 2$ , $(k+1)^2 < (k+1)^2 + 4\left (1 + \frac{k-1}{c^2} \right) < (k+1)^2 + k < (k+2)^2$ , so once again $n$ isn't an integer.

This post has been edited 1 time. Last edited by TechnoLenzer, May 10, 2022, 7:00 PM

Z K Y

The post below has been deleted. Click to close.

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

ZETA_in_olympiad

2211 posts

ZETA_in_olympiad

#35 h Jun 26, 2022, 9:28 AM

Y by

Assume the contrary then $a^2+\tfrac{4a^2+k}{b}=n^2$ with $b>k.$ Set $n=\tfrac{x+y}{2}$ and $a=\tfrac{x-y}{2}$ thus $x^2+y^2-$ $bxy-2xy+k=0.$ Fix $b$ and $k$ and take positive integer solutions $(x,y)$ such that $x+y$ is minimal. WLOG $x\geq y.$ By vieta jumping we have another solution $(z,y)=$ $(\tfrac{y^2+k}{x},y)=$ $((b+2)y-x,y).$ Note that $z$ is also a positive integer. Note that $x^2-y^2>(x-y)^2.$ But we have $b>k=bxy-(x-y)^2$ which implies $(x-y)^2>b>k.$ So $x>\tfrac{y^2+k}{x}= z,$ a contradiction with minimality.

This post has been edited 2 times. Last edited by ZETA_in_olympiad, Jun 26, 2022, 9:34 AM

Z K Y

The post below has been deleted. Click to close.

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

JAnatolGT_00

559 posts

JAnatolGT_00

#36 h Aug 30, 2022, 11:58 AM

Y by

Assume the opposite, so $a^2+\frac{4a^2+\epsilon}{b}=c^2$ for $c\in \mathbb{Z}^+,\epsilon \in [0;b)$ . Let $m=c-a,n=c+a$ , so $(n-m)^2+\epsilon =bmn\implies n^2-(2+b)mn+(m^2+\epsilon )=0 \text{ } (\bigstar)$ Note that $n_0=(2+b)-n=\frac{m^2+\epsilon}{n}\in \mathbb{Z}^+,$ so minimizing equality $\bigstar$ by $n$ we obtain $n\leq \frac{m^2+\epsilon}{n}\implies 4a^2<4ac=n^2-m^2\leq \epsilon<b.$ Therefore $c^2=a^2+1,$ which is absurd, thus the contradiction.

Z K Y

The post below has been deleted. Click to close.

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

akasht

84 posts

akasht

#37 h Nov 3, 2022, 6:57 AM • 1 Y

Y by sabkx

We shall show the related expression $a^2+4\left\lceil\frac{a^2}b\right\rceil$ can never be a perfect square. Suppose otherwise, and consider the smallest $a$ for which such an expression is a perfect square, and say $a^2+4\left\lceil\frac{a^2}b\right\rceil=(a+y)^2$ . Then $4\left\lceil\frac{a^2}b\right\rceil = 2ay + y^2$ . Clearly $y$ is even, so letting $y=2x$ we get that $\left \lceil \frac{a^2}{b} \right \rceil = ax+x^2$

Claim: $b= \left \lfloor \frac{a}{x} \right \rfloor$

Proof: We have the inequalities $b(ax+x^2-1) < 4a^2 \le b(ax+x^2)$ Observe that $\frac{a}{x} \cdot (ax+x^2-1) = a^2+ax - \frac{a}{x} \ge a^2$ implying $b \le \frac{a}{x}$ . On the other hand, $(\frac{a}{x} -1)(ax+x^2) = a^2 - x^2 < a^2 \implies b > \frac{a}{x}-1$ Since $b$ is an integer, $b= \left \lfloor \frac{a}{x} \right \rfloor$ as desired.

Next, let $a=bx+r$ . Then $\left\lceil\frac{a^2}b\right\rceil = ax+x^2 \implies \left\lceil\frac{b^2x^2+2bxr+r^2}{b} \right\rceil = (bx+r)x+x^2 \implies bx^2+2rx+ \left \lceil \frac{r^2}{b} \right \rceil = bx^2 + rx + x^2 \implies x^2-rx-\left \lceil \frac{r^2}{b} \right \rceil=0$
For the equation to have integer solutions in $x$ , the discriminant of this quadratic must be a perfect square, in other words $r^2+4\left\lceil \frac{r^2}{b} \right \rceil$ is a perfect square. But $r<a$ , contradicting the minimality of $a$ ! Thus $a^2+4\left\lceil\frac{a^2}b\right\rceil$ is never a perfect square.

To finish, observe that if $a^2+\left \lceil \frac{4a^2}{b} \right \rceil$ is a perfect square then $4a^2 + 4 \left \lceil \frac{4a^2}{b} \right \rceil = (2a)^2 + 4 \left \lceil \frac{(2a)^2}{b} \right \rceil$ is a perfect square, contradicting the earlier result.

This post has been edited 2 times. Last edited by akasht, Nov 3, 2022, 7:01 AM
Reason: Fixed LaTeX

Z K Y

The post below has been deleted. Click to close.

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

Olympikus

87 posts

Olympikus

#38 h Feb 23, 2023, 2:08 PM

Y by

Suppose it equals $(a+k)^2$ ( $k$ must be positive integer). First, I claim that $b = \left \lfloor \dfrac{2a}{k}\right \rfloor$ . Note that the problem condition is equivalent to
$-1< \frac{4a^2}{b}-k^2-2ak \leqslant 0$ $\iff \frac{4a^2}{k^2+2ak} \leqslant b < \frac{4a^2}{k^2+2ak-1} \ \ \ \ \ \ (\clubsuit)$ But $\dfrac{4a^2}{k^2+2ak-1} \le \dfrac{2a}{k}$ , so $b\leqslant \lfloor \dfrac{2a}{k}\rfloor$ .
Now it suffices to prove that $b>\dfrac{2a}{k}-1$ . Using the left inequality of $(\clubsuit)$ ,

$b-\frac{2a}{k}\ge\frac{4a^2}{k^2+2ak} - \frac{4a^2}{2ak} = -\frac{4a^2k^2}{2ak(k^2+2ak)}>-1.$ This concludes the proof of the claim. Now write the euclidean division of $2a$ by $k$ :
$2a = kb+r,\ 0\le r<k$ $\implies k^2+2ak = \left\lceil \frac{(kb+r)^2}{b} \right \rceil =\left\lceil \frac{r^2}{b} \right \rceil+k^2b+2kr$ $\implies k^2+(kb+r)k = \left\lceil \frac{r^2}{b} \right \rceil+k^2b+2kr$ $\implies k^2-kr =\left\lceil \frac{r^2}{b} \right \rceil$ So in particular $r$ is positive. Now looking at the discriminant (as a quadratic on $k$ ), we get that
$r^2+4\left\lceil \frac{r^2}{b} \right \rceil = (r+2l)^2.$ Let $x>0$ be minimum such that $x^2+4\left\lceil \frac{x^2}{b} \right \rceil$ is a square.

$\implies x^2+4\left\lceil \frac{x^2}{b} \right \rceil = (x+2y)^2$
with $y>0$ . Hence,

$\left\lceil \frac{x^2}{b} \right \rceil = xy+y^2$ I claim $b = \lfloor\frac{x}{y}\rfloor$ .
$xy+y^2-1 < \frac{x^2}{b} \leqslant xy+y^2$ $\frac{x^2}{xy+y^2}\leqslant b < \frac{x^2}{xy+y^2-1}$ $\frac{x}{y}-1 <\frac{x^2}{xy+y^2}\leqslant b < \frac{x^2}{xy+y^2-1}\leqslant \frac{x}{y} \ \ \ \square$
So we can divide $x$ by $y$ :
$x = by+c.$
$\left\lceil \frac{(by+c)^2}{b} \right \rceil = (by+c)y+y^2$ $\left\lceil \frac{c^2}{b} \right \rceil = y^2-cy$ by the quadratic formula,
$c^2-4\left\lceil \frac{c^2}{b} \right \rceil$ is a square, a contradiction if $x>c>0$ . But $b,y>0 \implies c<x$ so $c=0$ .

$\implies xy = \left\lceil \frac{x^2}{b} \right \rceil = xy+y^2$
a contradiction.

Z K Y

The post below has been deleted. Click to close.

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

IAmTheHazard

5001 posts

IAmTheHazard

#39 h Feb 27, 2023, 3:44 PM

Y by

I groupsolved this many years ago but here I am again.

Suppose that it does equal a square, i.e.
$a^2+\left\lceil \frac{4a^2}{b}\right\rceil=c^2 \implies \left\lceil \frac{4a^2}{b}\right\rceil=c^2-a^2 \implies b(c^2-a^2-1)<4a^2\leq b(c^2-a^2).$ Motivated by the many squares, we perform the classic substitution $c+a= x$ and $c-a= y$ , so $a=\tfrac{x-y}{2}$ and the inequality miraculously becomes
$bxy-b<(x-y)^2\leq bxy.$ Thus $(x-y)^2=bxy-d \implies x^2-(b+2)xy+y^2+d=0$ where $0 \leq d < b$ .
We now apply the technique of Vieta jumping. For fixed $b$ and $d$ , suppose that there exist solutions in $\mathbb{Z}^+$ to the equation. Consider the pair $(x_1,y)$ of positive integers such that $x_1+y$ is minimal, and WLOG let $x_1>y$ ( $x=y$ means $0>bxy-b\geq 0$ : absurd). Viewing the equation as a quadratic in $x$ with $y$ fixed, we have two roots: one of which is $x_1$ and the other $x_2$ . Since $x_1+x_2$ and $x_1x_2$ are both positive integers, $x_2$ is a positive integer as well, so by minimality $x_2\geq x_1>y$ . Now we have
$x_1+x_2=(b+2)y \text{ and } x_1x_2=y^2+d<y^2+b.$ Since $x_1x_2$ increases if $x_1+x_2$ are fixed and $x_1$ and $x_2$ approach each other, from the first equation and the fact that $x_1\geq y$ ,
$x_1x_2\geq (b+1)y^2,$ so $y^2+b>(b+1)y^2 \implies b>by^2$ , which is absurd. Hence no solutions can exist, implying that the expression given in the problem statement can never be a perfect square. $\blacksquare$

Z K Y

The post below has been deleted. Click to close.

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

Leo.Euler

577 posts

Leo.Euler

#40 h Apr 14, 2023, 1:29 AM

Y by

Suppose that $a^2+\left\lceil\frac{4a^2}b\right\rceil$ is a perfect square for some choice of $a$ and $b$ . Then, this is $a^2 + \frac{4a^2+m}{b} = k^2$ for some $0 \le m < b$ . This can be rewritten as $(b+4)a^2 - bk^2 = -m.$ Using the well-known substitution $k = \frac{x+y}{2}$ and $a = \frac{x-y}{2}$ , this becomes a Diophantine equation with the LHS a quadratic form in $x$ and $y$ : $x^2 - (b+2)xy + y^2 = -m.$ It suffices to prove that this has no solutions for $x \ge y \ge 1$ , which can be shown using Vieta jumping. Define the transform $T$ so that $T(x,y) =\left( y, \frac{y^2+m}{x} \right) = (y, (b+2)y-x)$ for $x, y \ge 1$ ; note that $T(x, y)$ is a solution to $x^2 - (b+2)xy + y^2 = -m$ if $(x, y)$ is a solution. If $xy \ge 2$ , then $(x-y)^2 > bxy-m > bxy-b \ge b,$ from which $x^2-y^2 = (x-y)(x+y) > (x-y)^2 > b > m.$ Thus, $0 < \frac{y^2+m}{x} < x$ for all $(x, y)$ with $xy \ge 2$ .

Now, for a given solution $(x, y)$ with $xy \ge 2$ , repeatedly apply $T$ ; each time, a valid solution $(x_n, y_n)$ with $x_n, y_n \ge 1$ and $\max(x_n, y_n)<\max(x_{n-1}, y_{n-1})$ is generated. Clearly an infinitude of solutions is obtained by this. However, the maximum of the numbers in the pair eventually hits $1$ , after which no solution can be generated. Thus no $(x, y)$ with $xy \ge 2$ works. Hence, $(x, y)=(1, 1)$ is the only possible solution, but this implies $b=m$ , so it doesn't work. All in all, there are no solutions $(a, b)$ to the original Diophantine equation, as desired.

This post has been edited 4 times. Last edited by Leo.Euler, Apr 14, 2023, 1:40 AM

Z K Y

The post below has been deleted. Click to close.

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

megarnie

5608 posts

megarnie

#41 h May 8, 2023, 2:25 PM

Y by

Suppose it was a perfect square for some $a,b$ .

Let $\frac{4a^2 + c}{b} = \left \lceil \frac{4a^2}{b} \right\rceil$ , where $0\le c< b$ .

The equation becomes $a^2 + \frac{4a^2 + c}{b} = d^2,$ where $d$ is a positive integer.

Multiplying both sides by $b$ gives $(b+4)a^2 - b d^2 = -c$ .

Obviously $d>a$ , so let $x = d+a$ , and $y = d-a$ , so that $d = \frac{x+y}{2}$ and $a = \frac{x-y}{2}$ and $x,y$ are positive integers.

After multiplying both sides by $4$ , the equation becomes $(b+4)(x-y)^2 - b (x+y)^2 = -4c$ , so $x^2 - (b+2)xy + y^2 = -c$
Notice that if $(x,y)$ is a solution (where $x>y$ ), then we get another solution $((b+2)y -x, y) = \left( \frac{y^2 + c}{x}, y \right)$
Claim: Either $(x,y) = (1,1)$ or $c< x^2 - y^2$ .
Proof: Suppose $(x,y)\ne (1,1)$ , so $xy\ge 2$ . We have $\begin{align*} x^2 - y^2 = (x-y)(x+y) > (x-y)^2 \\ = bxy - c > bxy - b \\ \ge b > c, \\ \end{align*}$ as desired. $\square$

Thus, if $xy>1$ , $0< \frac{y^2 + c}{x} < x$ which means we have another solution with lower maximum value. Thus we can keep repeating such an operation until we get $(1,1)$ is a solution. However, now $2 - (b+2) = -c$ , which means $b = c$ , which we know isn't true. Therefore there are no solutions.

This post has been edited 1 time. Last edited by megarnie, May 8, 2023, 2:33 PM

Z K Y

The post below has been deleted. Click to close.

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

bryanguo

1032 posts

bryanguo

#42 h May 10, 2023, 5:44 AM

Y by

nice

Suppose for the sake of contradiction the expression can take on square values. This is equivalent to $a^2+\frac{4a^2+c}{b} = k^2,$ where $k$ is a positive integer, and $c$ takes on any value $0 \leq c <b.$ Rewrite this as $(b+4)a^2-bk^2=-c.$ Obviously, $k>a,$ so we use the clever substitution $a=\tfrac{x-y}{2}$ and $k=\tfrac{x+y}{2},$ where $x$ and $y$ take on positive integer values. Slogging through algebra: $(b+4)\left(\frac{(x-y)^2}{4}\right) - b\left(\frac{(x+y)^2}{4}\right) = -c \implies x^2-(b+2)xy+y^2=-c.$ We now Vieta Jump $(x,y) \to \left(y, \frac{y^2+c}{x}\right) = (y, (b+2)y-x).$ Suppose $(x,y) \neq (1,1).$ Then we prove $\tfrac{y^2+c}{x}<x.$ Observe that $xy \geq 2.$ From our quadratic in $x,$ we know $(x-y)^2-bxy=-c>-b \implies (x-y)^2>bxy-b \geq b > c.$ But $(x-y)^2<(x-y)(x+y)=x^2-y^2,$ implying $c<x^2-y^2.$ Therefore, if minimal $(x,y)$ were to exist, then our process terminates only when we reach the base pair $(x,y)=(1,1).$ Otherwise, using our transformation, we would be able to find a smaller pair. But when plugged back into our original equation, this yields $2-(b+2)=-c \implies b=c,$ which is absurd.

Z K Y

The post below has been deleted. Click to close.

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

asdf334

7585 posts

asdf334

#43 h Dec 6, 2023, 1:27 AM

Y by

Wow this solution is identical to #37 and #38. !!!!

(Also 2019 ISL N8)
Let $a$ and $b$ be two positive integers. Prove that the integer
$a^2+\left\lceil \frac{4a^2}{b}\right\rceil$ is not a square.

Wow, this is really interesting. There are no actual theorems used here, just some clever observations and a bit of luck.

Lemma: The quantity
$a^2+4\left\lceil \frac{a^2}{b}\right\rceil$ is not a perfect square.
Proof: Suppose otherwise. Take $k\ge 1$ . Write
$a^2+4\left\lceil \frac{a^2}{b}\right\rceil=(a+2k)^2\implies \left\lceil \frac{a^2}{b}\right\rceil = ak+k^2.$ Now comes the first clever observation. If $b\ge \frac{a}{k}$ , then
$\frac{a^2}{b}\le ak\implies \left\lceil \frac{a^2}{b}\right\rceil\le ak$ which can't happen. Likewise if $b\le \frac{a-k}{k}$ then
$\left\lceil \frac{a^2}{b}\right\rceil\ge \frac{a^2}{b}\ge \frac{a^2k}{a-k}>ak+k^2$ hence $b\in \left(\frac{a}{k}-1,\frac{a}{k}\right)$ . As a result $k\nmid a$ and
$b=\left\lfloor \frac{a}{k}\right\rfloor.$ Write $a=bk+c$ with $1\le c<k$ . Then
$\left\lceil \frac{a^2}{b}\right\rceil=ak+k^2\iff \left\lceil \frac{b^2k^2+2bkc+c^2}{b}\right\rceil=bk^2+kc+k^2$ so that
$bk^2+2kc+\left\lceil \frac{c^2}{b}\right\rceil=bk^2+kc+k^2\implies k^2-kc-\left\lceil \frac{c^2}{b}\right\rceil=0.$ Well, here's nice observation #2: since we have a quadratic with integer coefficients with an integer $k$ as the root, it follows that the discriminant
$c^2+4\left\lceil \frac{c^2}{b}\right\rceil$ is a square. But wait! This is analogous to the original expression with $a\to c$ (it's important that $c\ge 1$ ). If we prove that $c<a$ , we should have a contradiction (classic infinite descent argument). But now, $c<k$ and so we need to prove $k\le a$ , which is obvious from
$a^2\ge \left\lceil \frac{a^2}{b}\right\rceil=ak+k^2.$ The lemma is proven.

It might seem strange that we just moved the $4$ outside, but it turns out the case where $4$ is inside is analogous. Write
$a^2+\left\lceil \frac{4a^2}{b}\right\rceil=(a+k)^2=a^2+2ak+k^2$ and now
$\left\lceil \frac{4a^2}{b}\right\rceil=2ak+k^2$ so we've just taken $a\to 2a$ and may proceed with the same strategy as used in the lemma. Done!

This post has been edited 2 times. Last edited by asdf334, Dec 6, 2023, 1:38 AM

Z K Y

The post below has been deleted. Click to close.

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

ihategeo_1969

235 posts

ihategeo_1969

#44 h Jun 2, 2024, 7:32 AM

Y by

My Vieta Jump is a bit different than the ones posted, so hopefully I am not wrong. (and if irs right, then yay my first N8!

)

Assume not. Call $(a,b)$ good if it satisfies the above equation. Extend the domain of $a$ to non-zero integers. See that $(a,b)$ is good if and only if $(-a,b)$ is good.

Let $(a,b)=(c,d)$ be the minimal solution which works with $c>0$ (so in other words $c+d$ is minimal). Let $X^2=c^2+\left\lceil\frac{4c^2}d\right\rceil \iff d(X^2-c^2)=4c^2+r \text{ for some $0 \leq r < d$}$ $\iff 4c^2-2cdk+r-dk^2=0$ with $X=c+k$ with $k>0$ obviously. Let $-c'=\frac{r-dk^2}{4c}=\frac{dk}2-c$ now see that $c'$ satisfies $X^2={(c')}^2+\left\lceil\frac{4{(c')}^2}d\right\rceil$ and since $c'$ is obviously rational, it must be an integer. And it is positive as well as $r<d \leq dk^2$ . And so $(c',d)$ is also good with $c \in \mathbb{N}$ and hence we get $c \leq c' = \frac{dk^2-r}{4c} \iff 4c^2 \leq dk^2-r \leq dk^2$ $\implies \frac{4c^2}d \leq k^2 \iff \left\lceil\frac{4c^2}d\right\rceil \leq k^2$ $\implies X^2={(c+k)}^2 \leq c^2+k^2$ which is a clear contradiction, as desired.

Z K Y

The post below has been deleted. Click to close.

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

Sammy27

83 posts

Sammy27

#45 h Jun 17, 2024, 8:23 PM • 1 Y

Y by Eka01

Storage

This post has been edited 1 time. Last edited by Sammy27, Jun 17, 2024, 8:30 PM

Z K Y

The post below has been deleted. Click to close.

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

S1muelJ

247 posts

S1muelJ

#46 h Jun 17, 2024, 8:33 PM

Y by

ihategeo_1969 wrote:

My Vieta Jump is a bit different than the ones posted, so hopefully I am not wrong. (and if irs right, then yay my first N8!

)

Assume not. Call $(a,b)$ good if it satisfies the above equation. Extend the domain of $a$ to non-zero integers. See that $(a,b)$ is good if and only if $(-a,b)$ is good.

Let $(a,b)=(c,d)$ be the minimal solution which works with $c>0$ (so in other words $c+d$ is minimal). Let $X^2=c^2+\left\lceil\frac{4c^2}d\right\rceil \iff d(X^2-c^2)=4c^2+r \text{ for some $0 \leq r < d$}$ $\iff 4c^2-2cdk+r-dk^2=0$ with $X=c+k$ with $k>0$ obviously. Let $-c'=\frac{r-dk^2}{4c}=\frac{dk}2-c$ now see that $c'$ satisfies $X^2={(c')}^2+\left\lceil\frac{4{(c')}^2}d\right\rceil$ and since $c'$ is obviously rational, it must be an integer. And it is positive as well as $r<d \leq dk^2$ . And so $(c',d)$ is also good with $c \in \mathbb{N}$ and hence we get $c \leq c' = \frac{dk^2-r}{4c} \iff 4c^2 \leq dk^2-r \leq dk^2$ $\implies \frac{4c^2}d \leq k^2 \iff \left\lceil\frac{4c^2}d\right\rceil \leq k^2$ $\implies X^2={(c+k)}^2 \leq c^2+k^2$ which is a clear contradiction, as desired.

Z K Y

The post below has been deleted. Click to close.

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

HamstPan38825

8866 posts

HamstPan38825

#47 h Aug 23, 2024, 10:50 PM

Y by

this is like the most canonical Vieta jumping problem I've ever seen

Let $\frac{4a^2+r}b \in \mathbb Z$ with $0 \leq r < p-1$ . The condition is equivalent to writing
$a^2b+4a^2+r = k^2b.$ Using the substitution $(a, k) = \left(\frac{m-n}2, \frac{m+n}2\right)$ with $m > n$ positive integers, the equation rewrites as $m^2+n^2-(b+2)mn+r=0.$ Consider the solution $(m_0, n_0)$ to this equation with $m_0+n_0$ minimal. As both $\left(\frac{n_0^2+r}{m_0}, n_0\right)$ is also a solution, it follows that $m_0^2 - n_0^2 \leq r$ , implying $m_0 \leq \frac{r+1}2 < \frac{b+1}2$ . In particular, $a \leq \frac b2$ , so $\frac{4a^2}b \leq 2a$ , i.e. $a^2 + \left \lceil \frac{4a^2}b \right \rceil < (a+1)^2$ , contradiction.