42nd International Mathematical Olympiad

IMO 2001 Problems and Solutions

Problem 6

ac + 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.

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². Let ABC = , so that CDA = 180°-. Applying the Law of Cosines to triangles ABC and ACD gives

Hence 2 cos = (a² + d² - b² - c²)/(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).