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

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\] (Error compiling LaTeX. ! Misplaced alignment tab character &.)`
`\[-K^2+KM+L^2+LN+KM-M^2+LN+N^2&=&KM+LN\] (Error compiling LaTeX. ! Misplaced alignment tab character &.)`
`\[L^2+LN+N^2&=&K^2-KM+M^2\] (Error compiling LaTeX. ! Misplaced alignment tab character &.)`

So, we have:

`\[(KM+LN)(L^2+LN+N^2)&=&KM(L^2+LN+N^2)+LN(L^2+LN+N^2)\] (Error compiling LaTeX. ! Misplaced alignment tab character &.)`
`\[&=&KM(L^2+LN+N^2)+LN(K^2-KM+M^2)\] (Error compiling LaTeX. ! Misplaced alignment tab character &.)`
`\[&=&KML^2+KMN^2+K^2LN+LM^2N\] (Error compiling LaTeX. ! Misplaced alignment tab character &.)`
`\[&=&(KL+MN)(KN+LM)\] (Error compiling LaTeX. ! Misplaced alignment tab character &.)`

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.

 2001 IMO (Problems) • Resources Preceded byProblem 5 1 • 2 • 3 • 4 • 5 • 6 Followed byProblem 6 All IMO Problems and Solutions