Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2005 Alabama ARML TST Problems/Problem 14"

(→‎See also)
(→‎Solution)
 
(3 intermediate revisions by 3 users not shown)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
−
<math>x^2-2y^2=1</math> means that <math>x</math> is odd. We can let <math>x=2x_1-1</math>:
+
===Solution 1===
 +
<math>x^2-2y^2=1</math> means that <math>x</math> is odd. We can let <math>x=2x_1-1</math> for some <math>x_1>0</math>:
  
 
<cmath>4x_1^2-4x_1-2y^2=0\Longrightarrow 2x_1^2-2x_1=y^2</cmath>
 
<cmath>4x_1^2-4x_1-2y^2=0\Longrightarrow 2x_1^2-2x_1=y^2</cmath>
  
−
y is even, <math>y=2y_1</math>.
+
y is even, <math>y=2y_1</math> for some <math>y_1>0</math>.
  
−
<cmath>2x_1^2-2x_1=4y_1^2\Longrightarrow x_1^2-x_1=x_1(x_1-1)=2y^2</cmath>
+
<cmath>2x_1^2-2x_1=4y_1^2\Longrightarrow x_1^2-x_1=x_1(x_1-1)=2y_1^2</cmath>
  
 
We need to find all integers <math>x_1</math> such that <math>x_1(x_1-1)</math> is twice a perfect square.
 
We need to find all integers <math>x_1</math> such that <math>x_1(x_1-1)</math> is twice a perfect square.
  
−
Since <math>x_1</math> and <math>x_1-1</math> are relatively prime, then either <math>x_1</math> is a perfect square or twice a perfect square, and the same for <math>x_1-1</math>.
+
Since <math>x_1</math> and <math>x_1-1</math> 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.
  
−
Let's say that <math>x_1</math> is the perfect square. Then x_1 is odd. We check some:
+
We will now find four smallest solutions for <math>x_1</math>. Obviously, these will give the four smallest solutions for <math>x+y</math>.
  
−
<math>x_1=9</math> works.
+
Each time we examine whether the value <math>y_1=\sqrt{\frac{x_1(x_1-1)}2}</math> is a positive integer.
  
−
<math>x_1=289</math> also works.
+
* <math>x_1=1</math> gives <math>y_1=0</math> which is not positive.
 +
* <math>x_1-1=1</math> gives <math>y_1=1</math>, hence <math>(x,y)=(3,2)</math>.
 +
* <math>x_1=9</math> gives <math>y_1=6</math>, hence <math>(x,y)=(17,12)</math>.
 +
* <math>x_1-1=9</math> gives <math>y_1=\sqrt{9\cdot 5}</math>.
 +
* <math>x_1=25</math> gives <math>y_1=\sqrt{25\cdot 12}</math>.
 +
* <math>x_1-1=25</math> gives <math>y_1=\sqrt{25\cdot 13}</math>.
 +
* <math>x_1=49</math> gives <math>y_1=\sqrt{49\cdot 24}</math>.
 +
* <math>x_1-1=49</math> gives <math>y_1=\sqrt{49\cdot 25}=35</math>, hence <math>(x,y)=(99,70)</math>.
 +
* <math>x_1=81</math> gives <math>y_1=\sqrt{81\cdot 40}</math>.
 +
* <math>x_1-1=81</math> gives <math>y_1=\sqrt{81\cdot 41}</math>.
 +
* <math>x_1=121</math> gives <math>y_1=\sqrt{121\cdot 60}</math>.
 +
* <math>x_1-1=121</math> gives <math>y_1=\sqrt{121\cdot 61}</math>.
 +
* <math>x_1=169</math> gives <math>y_1=\sqrt{169\cdot 84}</math>.
 +
* <math>x_1-1=169</math> gives <math>y_1=\sqrt{169\cdot 85}</math>.
 +
* <math>x_1=225</math> gives <math>y_1=\sqrt{225\cdot 112}</math>.
 +
* <math>x_1-1=225</math> gives <math>y_1=\sqrt{225\cdot 113}</math>.
 +
* <math>x_1=289</math> gives <math>y_1=\sqrt{289\cdot 144}=17\cdot 12 = 204</math>, hence <math>(x,y)=(577,408)</math>, and the answer is <math>x+y=\boxed{985}</math>.
  
−
We should be able to find some smaller ones when <math>x_1</math> is twice a perfect square, so we try that.
+
===Solution 2===
 +
We quickly find the first solution, <math>(x,y)=(3,2)</math>.  Factoring, we get
 +
<cmath>(3-2\sqrt{2})(3+2\sqrt{2})=1</cmath>
 +
We can square both sides to get
 +
<cmath>(3-2\sqrt{2})^2(3+2\sqrt{2})^2=1^2 \Rightarrow (17-12\sqrt{2})(17+12\sqrt{2})=1</cmath>
 +
So <math>(x,y)=(17,12)</math> is another solution.
  
−
<math>x_1=2</math> works.
+
This gives us a way to generate whatever solutions we want to the equation.  Raising the first equation to the fourth power gives us
 +
<cmath>(577-408\sqrt{2})(577+408\sqrt{2})=1</cmath>
 +
The answer is <math>577+408=\boxed{985}</math>.
  
−
<math>x_1=50</math> works.
+
====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.
−
We need to make sure that there is no others below 289. We check all other twice perfect squares, so 289 is the smallest <math>x_1</math>, and then <math>y_1=204</math>. Then we get <math>x=577</math> and <math>y=408</math>. <math>x+y=\boxed{985}</math>.
 
  
 
==See also==
 
==See also==

Latest revision as of 13:10, 26 August 2025

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.

See also

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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_Alabama_ARML_TST_Problems/Problem_14&oldid=258953"