42nd International Mathematical OlympiadIMO 2001 Problems and SolutionsWashinton, DC, USAJuly 1-14, 2001 Problem 6Let a, b, c, d be integers with a > b > c > d > 0. Suppose thatac + bd = (b + d + a - c)(b + d - a + c). Prove that ab + cd is not prime. Solution 1 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
a contradiction. Since a contradiction is reached in both (i) and (ii), ab + cd is not prime.
Solution 2 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 BD^{2}. Let ABC = , so that CDA = 180°-. Applying the Law of Cosines to triangles ABC and ACD gives
Hence 2 cos = (a^{2} + d^{2} - b^{2} - c^{2})/(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). |