42nd International Mathematical Olympiad
IMO 2001 Problems and SolutionsWashinton, DC, USA
July 1-14, 2001
Problem 6Let a, b, c, d be integers with a > b > c > d > 0. Suppose that
ac + bd = (b + d + a - c)(b + d - a + c).
Prove that ab + cd is not prime.
Suppose to the contrary that ab + cd is prime. Note that
for some positive integer m. By assumption, either m = 1 or gcd(a + d, b - c) = 1. We consider these alternatives in turn.Case (i): m = 1. Then
which is false.
Case (ii): gcd(a + d, b - c) = 1. Substituting ac + bd = (a + d)b - (b - c)a for the left-hand side of ac + bd = (b + d + a - c)(b + d - a + c), we obtain
In view of this, there exists a positive integer k such that
Adding these equations, we obtain a + b = k(a + b - c + d) and thus k(c - d) = (k - 1)(a + b). Recall that a > b > c > d. If k = 1 then c = d, a contradiction. If k >= 2 then
Since a contradiction is reached in both (i) and (ii), ab + cd is not prime.
The equality ac + bd = (b + d + a - c)(b + d - a + c) is equivalent to
Let ABCD be the quadrilateral with AB = a, BC = d, CD = b, AD = c, BAD = 60°, and BCD = 120°. Such a quadrilateral exists in view of (1) and the Law of Cosines; the common value in (1) is BD2. Let ABC = , so that CDA = 180°-. Applying the Law of Cosines to triangles ABC and ACD gives
Hence 2 cos = (a2 + d2 - b2 - c2)/(ad + bc), and
Because ABCD is cyclic, Ptolemy's Theorem gives
It follows that
(Note. Also straightforward algebra can be used obtain (2) from (1).) Next observe that
The first inequality follows from (a - d)(b - c) > 0, and the second from (a - b)(c - d) > 0.
Now assume that ab + cd is prime. It then follows from (3) that ab + cd and ac + bd are relatively prime. Hence, from (2), it must be true that ac + bd divides ad + bc. However, this is impossible by (3). Thus ab + cd must not be prime.
Note. Examples of 4-tuples (a, b, c, d) that satisfy the given conditions are (21, 18, 14, 1) and (65, 50, 34, 11).