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"

(Created page with "Problem 7 Let <math>n</math> be a positive integer. Show that the equation<cmath>\sqrt{x}+\sqrt{y}=\sqrt{n}</cmath>have solution of pairs of positive integers <math>(x,y)</mat...")
 
Line 1: Line 1:
−
Problem 7
+
==Problem==
 
Let <math>n</math> be a positive integer. Show that the equation<cmath>\sqrt{x}+\sqrt{y}=\sqrt{n}</cmath>have solution of pairs of positive integers <math>(x,y)</math> if and only if <math>n</math> is divisible by some perfect square greater than <math>1</math>.
 
Let <math>n</math> be a positive integer. Show that the equation<cmath>\sqrt{x}+\sqrt{y}=\sqrt{n}</cmath>have solution of pairs of positive integers <math>(x,y)</math> if and only if <math>n</math> is divisible by some perfect square greater than <math>1</math>.
  
−
test (sorry)
+
==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>.
 +
 
 +
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
 +
 
 +
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>a^2b+c^2b+2\sqrt{a^2b^2c^2=n</cmath>
 +
<cmath>a^2b+c^2b+2abc=n</cmath>
 +
<cmath>b(a^2+c^2+2ac)=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
 +
==See Also==
 +
{{Indonesia MO box|year=2012|num-b=6|num-a=8}}
 +
 
 +
[[Category:Intermediate Number Theory Problems]]

Revision as of 19:16, 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) fo$\sqrt{x}+\sqrt{y}=\sqrt{n}$.

Lets tackle the latter first, let$ (Error compiling LaTeX. Unknown error_msg)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€+\aqrt{p}=m\sqrt{p}\implies m\sqrt{p}=m\sqrt{p}$which is true, thus it is proven

For the first, let$ (Error compiling LaTeX. Unknown error_msg)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$. <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+2abc=n</cmath> <cmath>b(a^2+c^2+2ac)=n</cmath> <cmath>b(a+c)^2=n</cmath> since$ (Error compiling LaTeX. Unknown error_msg)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=237437"