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...")
 
 
(One intermediate revision by the same user not shown)
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}</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}+\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>.
 +
<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</math>, 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]]

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"