Difference between revisions of "2001 IMO Problems/Problem 6"

(Solution)
(Problem 6)
 
(5 intermediate revisions by 3 users not shown)
Line 3: Line 3:
  
 
==Solution==
 
==Solution==
{{solution}}
+
 
First, <math>(KL+MN)-(KM+LN)=(K-N)(L-M)>0</math> as <math>K>N</math> and <math>L>M</math>.  Thus, <math>KL+MN>KM+LN</math>.   
+
 
 +
First, <math>(KL+MN)-(KM+LN)=(K-N)(L-M)>0</math> as <math>K>N</math> and <math>L>M</math>.  Thus, <math>KL+MN>KM+LN</math>.   
  
 
Similarly, <math>(KM+LN)-(KN+LM)=(K-L)(M-N)>0</math> since <math>K>L</math> and <math>M>N</math>.  Thus, <math>KM+LN>KN+LM</math>.   
 
Similarly, <math>(KM+LN)-(KN+LM)=(K-L)(M-N)>0</math> since <math>K>L</math> and <math>M>N</math>.  Thus, <math>KM+LN>KN+LM</math>.   
Line 12: Line 13:
  
 
Now, we have:
 
Now, we have:
<cmath>(K+L-M+N)(-K+L+M+N)&=&KM+LN</cmath>
+
<cmath>(K+L-M+N)(-K+L+M+N)=KM+LN</cmath>
<cmath>-K^2+KM+L^2+LN+KM-M^2+LN+N^2&=&KM+LN</cmath>
+
<cmath>-K^2+KM+L^2+LN+KM-M^2+LN+N^2=KM+LN</cmath>
<cmath>L^2+LN+N^2&=&K^2-KM+M^2</cmath>
+
<cmath>L^2+LN+N^2=K^2-KM+M^2</cmath>
 
So, we have:
 
So, we have:
<cmath>(KM+LN)(L^2+LN+N^2)&=&KM(L^2+LN+N^2)+LN(L^2+LN+N^2)</cmath>
+
<cmath>(KM+LN)(L^2+LN+N^2)=KM(L^2+LN+N^2)+LN(L^2+LN+N^2)</cmath>
<cmath>&=&KM(L^2+LN+N^2)+LN(K^2-KM+M^2)</cmath>
+
<cmath>=KM(L^2+LN+N^2)+LN(K^2-KM+M^2)</cmath>
<cmath>&=&KML^2+KMN^2+K^2LN+LM^2N</cmath>
+
<cmath>=KML^2+KMN^2+K^2LN+LM^2N</cmath>
<cmath>&=&(KL+MN)(KN+LM)</cmath>
+
<cmath>=(KL+MN)(KN+LM)</cmath>
 
Thus, it follows that <cmath>(KM+LN) \mid (KL+MN)(KN+LM).</cmath>   
 
Thus, it follows that <cmath>(KM+LN) \mid (KL+MN)(KN+LM).</cmath>   
 
Now, since <math>KL+MN>KM+LN</math> if <math>KL+MN</math> is prime, then there are no common factors between the two.  So, in order to have <cmath>(KM+LN)\mid (KL+MN)(KN+LM),</cmath> we would have to have <cmath>(KM+LN) \mid (KN+LM).</cmath> This is impossible as <math>KM+LN>KN+LM</math>.  Thus, <math>KL+MN</math> must be composite.
 
Now, since <math>KL+MN>KM+LN</math> if <math>KL+MN</math> is prime, then there are no common factors between the two.  So, in order to have <cmath>(KM+LN)\mid (KL+MN)(KN+LM),</cmath> we would have to have <cmath>(KM+LN) \mid (KN+LM).</cmath> This is impossible as <math>KM+LN>KN+LM</math>.  Thus, <math>KL+MN</math> must be composite.

Latest revision as of 15:36, 20 December 2018

Problem 6

$K > L > M > N$ are positive integers such that $KM + LN = (K + L - M + N)(-K + L + M + N)$. Prove that $KL + MN$ is not prime.

Solution

First, $(KL+MN)-(KM+LN)=(K-N)(L-M)>0$ as $K>N$ and $L>M$. Thus, $KL+MN>KM+LN$.

Similarly, $(KM+LN)-(KN+LM)=(K-L)(M-N)>0$ since $K>L$ and $M>N$. Thus, $KM+LN>KN+LM$.

Putting the two together, we have \[KL+MN>KM+LN>KN+LM\]

Now, we have: \[(K+L-M+N)(-K+L+M+N)=KM+LN\] \[-K^2+KM+L^2+LN+KM-M^2+LN+N^2=KM+LN\] \[L^2+LN+N^2=K^2-KM+M^2\] So, we have: \[(KM+LN)(L^2+LN+N^2)=KM(L^2+LN+N^2)+LN(L^2+LN+N^2)\] \[=KM(L^2+LN+N^2)+LN(K^2-KM+M^2)\] \[=KML^2+KMN^2+K^2LN+LM^2N\] \[=(KL+MN)(KN+LM)\] Thus, it follows that \[(KM+LN) \mid (KL+MN)(KN+LM).\] Now, since $KL+MN>KM+LN$ if $KL+MN$ is prime, then there are no common factors between the two. So, in order to have \[(KM+LN)\mid (KL+MN)(KN+LM),\] we would have to have \[(KM+LN) \mid (KN+LM).\] This is impossible as $KM+LN>KN+LM$. Thus, $KL+MN$ must be composite.

See also

2001 IMO (Problems) • Resources
Preceded by
Problem 5
1 2 3 4 5 6 Followed by
Problem 6
All IMO Problems and Solutions
Invalid username
Login to AoPS