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 "2012 Indonesia MO Problems/Problem 7"
 
Line 4: Line 4:
 
==Solution==
 
==Solution==
  
−
Since iff is a double implication, we can prove that if there exists a positive integer solution <math>(x,y)</math> to <math>\sqrt{x}+\sqrt{y}=\sqrt{n}, then </math>n<math> is divisible by some perfect square greater than </math>1<math>, and if </math>n<math> is divisible by some perfect square greater than </math>1<math> then there exists a positive integer solution (x,y) fo </math>\sqrt{x}+\sqrt{y}=\sqrt{n}<math>.
+
Since iff is a double implication, we can prove that if there exists a positive integer solution <math>(x,y)</math> to <math>\sqrt{x}+\sqrt{y}=\sqrt{n}</math>, then <math>n</math> is divisible by some perfect square greater than <math>1</math>, and if <math>n</math> is divisible by some perfect square greater than <math>1</math> then there exists a positive integer solution (x,y) for <math>\sqrt{x}+\sqrt{y}=\sqrt{n}</math>.
  
−
Lets tackle the latter first, let </math>n=m^2p<math> where </math>m>1<math> and </math>p<math> is not divisible by any perfect square greater than </math>1<math>, let </math>x=p(m-1)^2<math> and </math>y=p(1)^2<math>. Substituting back in we can get </math>\sqrt{p(m-1)^2}+\sqrt{p(1)^2}=\sqrt{m^2p}\implies (m-1)\sqrt{p€+\aqrt{p}=m\sqrt{p}\implies m\sqrt{p}=m\sqrt{p}<math> which is true, thus it is proven
+
Lets tackle the latter first, let <math>n=m^2p</math> where <math>m>1</math> and <math>p</math> is not divisible by any perfect square greater than <math>1</math>, let <math>x=p(m-1)^2</math> and <math>y=p(1)^2</math>. Substituting back in we can get <math>\sqrt{p(m-1)^2}+\sqrt{p(1)^2}=\sqrt{m^2p}\implies (m-1)\sqrt{p}+\sqrt{p}=m\sqrt{p}\implies m\sqrt{p}=m\sqrt{p}</math> which is true, thus it is proven
  
−
For the first, let </math>x=a^2b<math> and </math>y=c^2d<math> where </math>b,d<math> are not divisible by a perfect square greater than </math>1<math>, </math>\sqrt{x}+\sqrt{y}=\sqrt{n}\implies x+y+2\sqrt{xy}=n<math>. Since </math>\sqrt{xy}<math> has to be an integer, then </math>xy<math> must be a perfect square, that means </math>a^2c^2bd<math> is a perfect square which means </math>bd<math> is a percect square, let </math>b=p_1p_2\dots p_i<math> where </math>p<math> are distinct primes, for </math>bd<math> to be a perfect square, </math>d<math> must be exactly </math>p_1p_2\dots p_i<math>, as if it were less there exists a </math>p_k<math> that divides </math>b<math> but not </math>d<math> and thus would not be a perfect square, the same logic would apply if </math>d<math> was bigger than </math>b<math>, thus </math>b=d<math>.  
+
For the first, let <math>x=a^2b</math> and <math>y=c^2d</math> where <math>b,d</math> are not divisible by a perfect square greater than <math>1</math>, <math>\sqrt{x}+\sqrt{y}=\sqrt{n}\implies x+y+2\sqrt{xy}=n</math>. Since <math>\sqrt{xy}</math> has to be an integer, then <math>xy</math> must be a perfect square, that means <math>a^2c^2bd</math> is a perfect square which means <math>bd</math> is a percect square, let <math>b=p_1p_2\dots p_i</math> where <math>p</math> are distinct primes, for <math>bd</math> to be a perfect square, <math>d</math> must be exactly <math>p_1p_2\dots p_i</math>, as if it were less there exists a <math>p_k</math> that divides <math>b</math> but not <math>d</math> and thus would not be a perfect square, the same logic would apply if <math>d</math> was bigger than <math>b</math>, thus <math>b=d</math>.  
 
<cmath>x+y+2\sqrt{xy}=n</cmath>
 
<cmath>x+y+2\sqrt{xy}=n</cmath>
−
<cmath>a^2b+c^2b+2\sqrt{a^2b^2c^2=n</cmath>
+
<cmath>a^2b+c^2b+2\sqrt{a^2b^2c^2}=n</cmath>
 
<cmath>a^2b+c^2b+2abc=n</cmath>
 
<cmath>a^2b+c^2b+2abc=n</cmath>
 
<cmath>b(a^2+c^2+2ac)=n</cmath>
 
<cmath>b(a^2+c^2+2ac)=n</cmath>
 
<cmath>b(a+c)^2=n</cmath>
 
<cmath>b(a+c)^2=n</cmath>
−
since </math>a,c\geq 1\implies a+c\geq 2$, thus n is divisible by a perfect square greater than 1
+
since <math>a,c\geq 1\implies a+c\geq 2</math>, thus n is divisible by a perfect square greater than 1
 
==See Also==
 
==See Also==
 
{{Indonesia MO box|year=2012|num-b=6|num-a=8}}
 
{{Indonesia MO box|year=2012|num-b=6|num-a=8}}
  
 
[[Category:Intermediate Number Theory Problems]]
 
[[Category:Intermediate Number Theory Problems]]

Latest revision as of 19:19, 20 December 2024

Problem

Let $n$ be a positive integer. Show that the equation\[\sqrt{x}+\sqrt{y}=\sqrt{n}\]have solution of pairs of positive integers $(x,y)$ if and only if $n$ is divisible by some perfect square greater than $1$.

Solution

Since iff is a double implication, we can prove that if there exists a positive integer solution $(x,y)$ to $\sqrt{x}+\sqrt{y}=\sqrt{n}$, then $n$ is divisible by some perfect square greater than $1$, and if $n$ is divisible by some perfect square greater than $1$ then there exists a positive integer solution (x,y) for $\sqrt{x}+\sqrt{y}=\sqrt{n}$.

Lets tackle the latter first, let $n=m^2p$ where $m>1$ and $p$ is not divisible by any perfect square greater than $1$, let $x=p(m-1)^2$ and $y=p(1)^2$. Substituting back in we can get $\sqrt{p(m-1)^2}+\sqrt{p(1)^2}=\sqrt{m^2p}\implies (m-1)\sqrt{p}+\sqrt{p}=m\sqrt{p}\implies m\sqrt{p}=m\sqrt{p}$ which is true, thus it is proven

For the first, let $x=a^2b$ and $y=c^2d$ where $b,d$ are not divisible by a perfect square greater than $1$, $\sqrt{x}+\sqrt{y}=\sqrt{n}\implies x+y+2\sqrt{xy}=n$. Since $\sqrt{xy}$ has to be an integer, then $xy$ must be a perfect square, that means $a^2c^2bd$ is a perfect square which means $bd$ is a percect square, let $b=p_1p_2\dots p_i$ where $p$ are distinct primes, for $bd$ to be a perfect square, $d$ must be exactly $p_1p_2\dots p_i$, as if it were less there exists a $p_k$ that divides $b$ but not $d$ and thus would not be a perfect square, the same logic would apply if $d$ was bigger than $b$, thus $b=d$. \[x+y+2\sqrt{xy}=n\] \[a^2b+c^2b+2\sqrt{a^2b^2c^2}=n\] \[a^2b+c^2b+2abc=n\] \[b(a^2+c^2+2ac)=n\] \[b(a+c)^2=n\] since $a,c\geq 1\implies a+c\geq 2$, thus n is divisible by a perfect square greater than 1

See Also

2012 Indonesia MO (Problems)
Preceded by
Problem 6 		1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 Followed by
Problem 8
All Indonesia MO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2012_Indonesia_MO_Problems/Problem_7&oldid=237438"