2005 Alabama ARML TST Problems/Problem 14

Problem

Find the fourth smallest possible value of $x+y$ where x and y are positive integers that satisfy the following equation:

$x^2-2y^2=1$ .

Solution

Solution 1

$x^2-2y^2=1$ means that $x$ is odd. We can let $x=2x_1-1$ for some $x_1>0$ :

$4x_1^2-4x_1-2y^2=0\Longrightarrow 2x_1^2-2x_1=y^2$

y is even, $y=2y_1$ for some $y_1>0$ .

$2x_1^2-2x_1=4y_1^2\Longrightarrow x_1^2-x_1=x_1(x_1-1)=2y_1^2$

We need to find all integers $x_1$ such that $x_1(x_1-1)$ is twice a perfect square.

Since $x_1$ and $x_1-1$ are relatively prime, one of them is a perfect square and the other is twice a perfect square. Moreover, the perfect square must be odd.

We will now find four smallest solutions for $x_1$ . Obviously, these will give the four smallest solutions for $x+y$ .

Each time we examine whether the value $y_1=\sqrt{\frac{x_1(x_1-1)}2}$ is a positive integer.

$x_1=1$ gives $y_1=0$ which is not positive.
$x_1-1=1$ gives $y_1=1$ , hence $(x,y)=(3,2)$ .
$x_1=9$ gives $y_1=6$ , hence $(x,y)=(17,12)$ .
$x_1-1=9$ gives $y_1=\sqrt{9\cdot 5}$ .
$x_1=25$ gives $y_1=\sqrt{25\cdot 12}$ .
$x_1-1=25$ gives $y_1=\sqrt{25\cdot 13}$ .
$x_1=49$ gives $y_1=\sqrt{49\cdot 24}$ .
$x_1-1=49$ gives $y_1=\sqrt{49\cdot 25}=35$ , hence $(x,y)=(99,70)$ .
$x_1=81$ gives $y_1=\sqrt{81\cdot 40}$ .
$x_1-1=81$ gives $y_1=\sqrt{81\cdot 41}$ .
$x_1=121$ gives $y_1=\sqrt{121\cdot 60}$ .
$x_1-1=121$ gives $y_1=\sqrt{121\cdot 61}$ .
$x_1=169$ gives $y_1=\sqrt{169\cdot 84}$ .
$x_1-1=169$ gives $y_1=\sqrt{169\cdot 85}$ .
$x_1=225$ gives $y_1=\sqrt{225\cdot 112}$ .
$x_1-1=225$ gives $y_1=\sqrt{225\cdot 113}$ .
$x_1=289$ gives $y_1=\sqrt{289\cdot 144}=17\cdot 12 = 204$ , hence $(x,y)=(577,408)$ , and the answer is $x+y=\boxed{985}$ .

Solution 2

We quickly find the first solution, $(x,y)=(3,2)$ . Factoring, we get $(3-2\sqrt{2})(3+2\sqrt{2})=1$ We can square both sides to get $(3-2\sqrt{2})^2(3+2\sqrt{2})^2=1^2 \Rightarrow (17-12\sqrt{2})(17+12\sqrt{2})=1$ So $(x,y)=(17,12)$ is another solution.

This gives us a way to generate whatever solutions we want to the equation. Raising the first equation to the fourth power gives us $(577-408\sqrt{2})(577+408\sqrt{2})=1$ The answer is $577+408=\boxed{985}$ .

Solution 3

Step 1: Find the fundamental solution to the Pell's equation. The given equation, $x^{2}-2y^{2}=1$, is a Pell's equation of the form $x^{2}-Dy^{2}=1$ with $D=2$. The solutions are positive integers. By checking small integer values, we can find the fundamental solution $(x_{1},y_{1})$.If $y=1$, $x^{2}-2(1)^{2}=1\Rightarrow x^{2}=3$, no integer solution.If $y=2$, $x^{2}-2(2)^{2}=1\Rightarrow x^{2}=9\Rightarrow x=3$.Thus, the fundamental solution is $(x_{1},y_{1})=(3,2)$. Step 2: Generate subsequent solutions. Subsequent solutions $(x_{n},y_{n})$ can be found using the recursive relation:$x_{n+1}=x_{1}x_{n}+Dy_{1}y_{n}=3x_{n}+4y_{n}$$y_{n+1}=x_{1}y_{n}+y_{1}x_{n}=3y_{n}+2x_{n}$Or, alternatively, using the identity $x_{n}+y_{n}\sqrt{2}=(3+2\sqrt{2})^{n}$. Let's find the first four solutions and their corresponding $x+y$ values. First solution (n=1):$x_{1}=3,y_{1}=2$$x_{1}+y_{1}=3+2=5$ Second solution (n=2):$x_{2}+y_{2}\sqrt{2}=(3+2\sqrt{2})^{2}=9+12\sqrt{2}+8=17+12\sqrt{2}$.$x_{2}=17,y_{2}=12$$x_{2}+y_{2}=17+12=29$ Third solution (n=3):$x_{3}+y_{3}\sqrt{2}=(3+2\sqrt{2})^{3}=(17+12\sqrt{2})(3+2\sqrt{2})=51+34\sqrt{2}+36\sqrt{2}+48=99+70\sqrt{2}$.$x_{3}=99,y_{3}=70$$x_{3}+y_{3}=99+70=169$ Fourth solution (n=4):$x_{4}+y_{4}\sqrt{2}=(3+2\sqrt{2})^{4}=(99+70\sqrt{2})(3+2\sqrt{2})=297+198\sqrt{2}+210\sqrt{2}+280=577+408\sqrt{2}$.$x_{4}=577,y_{4}=408$$x_{4}+y_{4}=577+408=985$ Answer: The first four values of $x+y$ are 5, 29, 169, and 985. The fourth smallest value of $x+y$ is 985.

2005 Alabama ARML TST (Problems)
Preceded by: Problem 13	Followed by: Problem 15
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15

Page

Toolbox

Search