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"

(New page: ==Problem== Find the fourth smallest possible value of <math>x+y</math> where <i>x</i> and <i>y</i> are positive integers that satisfy the following equation:<center><math>x^2-2y^2=1</math...)
 
m (Root 2. Not 3.)
 
(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.
+
==See also==
 +
{{ARML box|year=2005|state=Alabama|num-b=13|num-a=15}}
  
−
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>.
+
[[Category:Intermediate Number Theory Problems]]
−
 
 
−
==See also==
 

Latest revision as of 22:41, 5 January 2014

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}$.

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=58658"