Positive integer $k(\ge 8)$ is given. Prove that if there exists a pair of positive integers $(x,y)$ that satisfies the conditions below, then there exists infinitely many pairs $(x,y)$. (1) $ $ $x\mid y^2-3, y\mid x^2-2$ (2) $ $ $gcd\left(3x+\frac{2(y^2-3)}{x},2y+\frac{3(x^2-2)}{y}\right)=k$ $ $
Problem
Source: FKMO 2021 Problem 2
Tags: Diophantine equation, number theory, FKMO
08.05.2021 20:49
Any ideas? Pell equation?
10.05.2021 14:49
Sketch of proof: When $k$ is odd, the pairs satisfying the condition are the pairs satisfying $3x^2+2y^2-6=kxy$ with $x$ odd, $(y, 3)=1$. When $k$ is even(actually $k$ is a multiple of 4), the condition is equivalent to $3x^2+2y^2-6=kxy$ with $x\equiv 2(mod 4)$, $(y, 3)=1$. There are infinitely many solutions because it is a Pell equation, and the solutions of the pell equations form a cycle modulo $m$ for any $m$. You might need to do something about the solution being positive(I did on the test but I don't know if it's necessary)
11.05.2021 05:47
(Almost)Full Solution Let $(x, y)$ be a solution such that $x | y^2-3$, $y | x^2-2$ and $gcd\left(3x+\frac{2(y^2-3)}{x}, 2y+\frac{3(x^2-2)}{y}\right)=k$. From $y | x^2-2$ we have $(y, 3)=1$, and from $x|y^2-3$ we have $4\nmid x$. Also letting $g=gcd(x, y)$, we have $g|2$, $g|3$ hence $g=1$. Now the gcd condition can be written as $gcd\left(\frac{3x^2+2y^2-6}{x}, \frac{3x^2+2y^2-6}{y}\right)=\frac{3x^2+2y^2-6}{xy}=k$, and $3x^2+2y^2-kxy=6$. ---(1) If the given $x$ is odd, $ky=3x+2\times\frac{y^2-3}{x}$ is odd and hence $k$ is odd. If the given $x$ is even, we have $x\equiv 2(mod 4)$ because $4\nmid x$, and $y$ is odd because $x | y^2-3$. Writing equation (1) as $3x^2+2y^2-6=kxy$, the left hand side is $0(mod 8)$, but $xy$ has only one power of two, hence $4|k$. So there are two cases, $k$ even and $k$ odd. Case 1: $k$ is odd. In this case, The given $x$ is also odd. Claim: A pair of positive integers($\geq 2$) such that $3x^2+2y^2-6=kxy$ and $2\nmid x$, $3\nmid y$ satisfies the condition of the problem.
Let us show that there are infinitely many positive integers such that $3x^2+2y^2-kxy=6$ with $2\nmid x$, $3\nmid y$. The equation can be written as $16y^2-8kxy+24x^2=48$, and $(4y-kx)^2-(k^2-24)x^2=48$, which is now a pell equation. $k^2-24$ is not a square because $k\geq 8$. Let $Y=4y-kx$ and $X=x$, $d=k^2-24$. Then $Y^2-dX^2=48$. Note that $Y$ can be positive or negative. Also the original variables are $x=X$ , and $y=\frac{Y+kX}{4}$. We need to show there are infinitely many (not neccesarily positive) integer solutions to $Y^2-dX^2=48$ such that $2\nmid X$ is positive, $\frac{Y+kX}{4}$ is a positive integer, and also $3\nmid \frac{Y+kX}{4}$. There exists a solution of positive integers $(\alpha, \beta)$ such that $\beta^2-d\alpha^2=1$. (Well-known) Let the original given solution be $(X_1, Y_1)$. First consider the case where $Y_1>0$. (We have always $X_1>0$). In this case, we define $Y_n+\sqrt{d}X_n = (Y_1+\sqrt{d}X_1)(\beta+\sqrt{d}\alpha)^{n-1}$. We have the recurrence relation $Y_{n+1}=\beta Y_n+d\alpha X_n$, $X_{n+1}=\alpha Y_n+\beta X_n$. Since $Y_1>0$ we have $X_n, Y_n>0$ and also the solutions are increasing and hence are all distinct. In this case $Y_n+kX_n$ is always positive, and all we need is $2\nmid X_n$, $4|Y_n+kX_n$ and $(3, \frac{Y_n+kX_n}{4})=1$. There are infinitely many $n$ satisfying this condition, because of the following lemma.(Set $m=12$) Lemma. $(X_n, Y_n)$ cycles from the first term modulo $m$ for any positive integer $m$. proof. . In the other case where $Y_1<0$, we define a different sequence: $Y_n+\sqrt{d}X_n = (Y_1+\sqrt{d}X_1)(\beta-\sqrt{d}\alpha)^{n-1}$. We can see that $(-Y_n)+\sqrt{d}X_n = (-Y_1+\sqrt{d}X_1)(\beta+\sqrt{d}\alpha)^{n-1}$, and since $-Y_1, X_1>0$, we have $X_n>0, Y_n<0$ for all $n$ and $X_n$ is increasing so the solutions are all distinct. We also need to check that $Y_n+kX_n>0$. This is because $Y_n^2=48+dX_n^2=48+(k^2-24)X_n^2<(kX_n)^2$ when $X_n>1$. Hence by using the lemma again we have our conclusion. Case 2: $k$ is even. In this case, we know that $x\equiv 2(mod 4)$ and $(y,3)=1$. Similar to case 1 we observe the following claim:(In this claim the fact that $k$ is even is needed, unlike the first case.) Claim: $k$ is even. A pair of positive integers($\geq 2$) such that $3x^2+2y^2-6=kxy$ and $x\equiv 2(mod 4)$, $3\nmid y$ satisfies the condition of the problem.
Now we proceed in the same way as Case 1 and conclude that there are infinitely many solutions satisfying the above conditions.
11.05.2021 15:07
Just a short sketch of what I wrote in the test. claim1) $(x,y)$ satisfies the problem's condition if and only if $3x^2+2y^2-6=kxy$ and $2\nmid x$, $3\nmid y$. claim2) There is infinitely many pairs $(x,y)$ that satisfies $3x^2+2y^2-6=kxy$ and $2\nmid x$, $3\nmid y$. I used Vieta Jumping to prove claim2)..
12.05.2021 05:06
@above I believe your claim 1) is wrong; Could you provide your reasoning? I think when $k=20$, there is a solution $(x, y)$ satisfying the problem's condition but $x$ is even. The reason being: according to wolframalpha(https://www.wolframalpha.com/input/?i=x%5E2-94y%5E2%3D12+over+integers), the equivalent pell equation $x^2-94y^2=12$ has a solution over the integers(Although not a computable size, hence not possible to find on the test). To me, splitting the cases $k$ even and odd was one of the main points of the problem. Also, I don't see how vieta jumping can be used for this equation.. I admit I'm not an expert in vieta jumping, but It looks like the other solution isn't an integer? (+I was very impressed that Wolframalpha could solve Pell equations)
09.07.2022 12:44
why you have this? Quasi07 wrote: (Almost)Full Solution Since $Y_1>0$ we have $X_n, Y_n>0$ and also the solutions are increasing and hence are all distinct. In this case $Y_n+kX_n$ is always positive, and all we need is $2\nmid X_n$, $4|Y_n+kX_n$ and $(3, \frac{Y_n+kX_n}{4})=1$.
05.02.2023 05:29
can you solve this problem with vieta jumping? i wonder if vieta jumping works when coefficients of x^2, y^2 terms are not 1
10.02.2023 19:39
02.03.2024 10:41
Notice that $(x,y)$ is a solution iff $x|y^2-3, y|x^2-2$, and $3x^2-2y^2-6=k lcm(x,y) = kxy$, as the former two implies $(x,y)=1$. Futhermore, $3x^2-2y^2-6 = kxy$ implies $x|(3x-ky)x=2y^2-6$ and similarly $y|3x^2-6$, so it suffices to prove there's infinite $(x,y)$ so that $3 \not | y$ and $2 \not |x$(we'll see the latter is too good to be true- we can still prove $x|y^2-3$ though). We invoke the solutions to Pell's equation, since $$3x^2-2y^2-6 = kxy \iff (4y-kx)^2 - (k^2-24)x^2 = 48,$$and $k^2-24$ is never a perfect square, (part of) the solutions are given by $$ \begin{pmatrix} \pm(4y-kx) \\\ x \end{pmatrix} = \begin{pmatrix} \pm(4y_0-kx_0) \\\ x_0 \end{pmatrix} \otimes (\begin{pmatrix} u_0 & (k^2-24)v_0 \\\ v_0 & u_0 \end{pmatrix}^n \begin{pmatrix} 1 \\\ 0 \end{pmatrix} ),$$where both the "$+$" sign is taken if $4y_0-kx_0 \geq 0$ and "$-$" if otherwise, $(u_0, v_0)$ is the least positive solution to $u^2 - (k^2-24)v^2=1$ and the operation "$\otimes$" is given by $$\begin{pmatrix} a \\\ b \end{pmatrix} \otimes \begin{pmatrix} c \\\ d \end{pmatrix} = \begin{pmatrix} ac+(k^2-24)bd \\\ ad+bc \end{pmatrix}.$$ This always generates positive reals $(x, y)$ for obvious reason. By direct calculation, this is equivalent to $\begin{pmatrix} x \\\ y \end{pmatrix} = \begin{pmatrix} u_0-kv_0 & 4v_0 \\\ -6v_0 & u_0+kv_0 \end{pmatrix}^n \begin{pmatrix} x_0 \\\ y_0 \end{pmatrix}$ for $4y-kx \geq 0$, or $\begin{pmatrix} x \\\ y \end{pmatrix} = \begin{pmatrix} u_0+kv_0 & -4v_0 \\\ 6v_0 & u_0-kv_0 \end{pmatrix}^n \begin{pmatrix} x_0 \\\ y_0 \end{pmatrix}$ for $4y-kx < 0$. In particular, this formula always gives **positive integers** $(x,y)$, and they are distinct for different $n \in \mathbb{N}$, as $|4y-kx|+|x|$ is strictly increasing. Denote this matrix by $A$. It then remains to check that if there are infinite such integer pairs that is both invertible mod 6 (this implies $2 \not |x$ and $3 \not |y$). In fact this is not generally true as mentioned- but we can prove weaker. $\det A = u_0^2-(k^2-24)v_0^2=1$, so $A$ is invertible over $Z/3Z$, and hence $A^n=I$ for some $n$. So we indeed have infinite solutions generated with $3 \not |y$, as $3 \not |y_0$(otherwise $x_0^2 \equiv -1 \text{ mod 3 }$) so after the $n$-th iteration $y \text{ mod 3 }$ will cycle back to the residue of $y_0$. Consider these solutions $(x,y)$ with $3 \not |y$. If $2 \not| x$, $x|2y^2-6 \implies x|y^2-3$ so we are done; If $2|x$, then $x \equiv 2 \text{ mod 4 }$, so $$2ky + 2y^2\equiv 3x^2+kxy+2y^2 = 6 \equiv 2 \text{ (mod 4).}$$So $2 | y(y+k)-1$, implying both $y$ and $y+k$ are odd, so $k$ is even $\implies$ $3x-ky$ is even, recall $(3x-ky)x = 2(y^2-3)$, so this is enough to deduce $x | y^2-3$. This finishes our proof.