Positive integer k(≥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∣y2−3,y∣x2−2 (2) gcd(3x+2(y2−3)x,2y+3(x2−2)y)=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 3x2+2y2−6=kxy with x odd, (y,3)=1. When k is even(actually k is a multiple of 4), the condition is equivalent to 3x2+2y2−6=kxy with x≡2(mod4), (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|y2−3, y|x2−2 and gcd(3x+2(y2−3)x,2y+3(x2−2)y)=k. From y|x2−2 we have (y,3)=1, and from x|y2−3 we have 4∤. 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.