USA IMO

First Solution. For the sake of contradiction, assume that $ab + cd$ is prime. Note that
$$ab + cd = (a + d)c + (b - c)a = m \cdot \gcd(a + d, b - c)$$
for some positive integer $m$. Writing $g = \gcd(a+d, b-c)$, we have
$$m = \frac{a+d}{g} \cdot c + \frac{b-c}{g} \cdot a \geq c+a > 1.$$
Therefore, because $ab+cd$ is prime, $g=1$.
Substituting $ac+bd = (a+d)b - (b-c)a$ for the left-hand side of the given condition, we obtain
$$(a+d)b - (b-c)a = (a+d)(b+d-a+c) + (b-c)(b+d-a+c),$$
or
$$(a+d)(a-c-d) = (b-c)(b+c+d).$$
Hence, there exists a positive integer $k$ such that
$$a-c-d = k(b-c),$$
$$b+c+d = k(a+d).$$
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 > 0$. If $k=1$, then $c=d$, a contradiction. If $k \ge 2$, then
$$2 \ge \frac{k}{k-1} = \frac{a+b}{c-d} > \frac{2b}{c} > 2,$$
a contradiction.
Therefore, our original assumption was wrong, and $ab+cd$ is not prime.

Second Solution. (By Yonggao Chen, China) We give a proof by contradiction. Assume that $p = ab+cd$ is prime. Then $ab \equiv -cd \pmod p$. By (1),
$$b^2(b^2 + bd + d^2) = b^2(a^2 - ac + c^2) = (ab)^2 - ab(bc) + b^2c^2.$$
It follows that
$$\begin{aligned} b^2(b^2 + bd + d^2) &\equiv (ab)^2 - ab(bc) + b^2c^2 \\ &\equiv (cd)^2 + cd(bc) + b^2c^2 \\ &\equiv c^2(b^2 + bd + d^2) \pmod p, \end{aligned}$$
implying that $p \mid (b^2 - c^2)(b^2 + bd + d^2)$. Observe that $0 < b^2 - c^2 < b^2 < ab < p$. Thus, $p$ and $b^2 - c^2$ must be relatively prime, so
$$p \mid (b^2 + bd + d^2). \qquad (2)$$
Because
$$0 < b^2 + bd + d^2 < ab + ab + cd = 2ab + cd < 2p,$$
we must have $b^2 + bd + d^2 = p = ab + cd$ or, equivalently,
$$b(b+d-a) = d(c-d).$$
Because $ab + cd$ is prime, $b$ must be relatively prime to $d$, so $b \mid c - d$. This is impossible, because $0 < c - d < b$.

Third Solution. (By Zhiqiang Zhang, China) Let $x = a - c$, $y = a + c$, $u = b - d$, and $v = b + d$. By the given condition, we have
$$\begin{aligned} y^2 - x^2 + v^2 - u^2 &= 4(ac + bd) \\ &= 4[(b+d) + (a-c)][(b+d) - (a-c)] \\ &= 4(v+x)(v-x) = 4(v^2 - x^2), \end{aligned}$$
or
$$y^2 - u^2 = 3(v^2 - x^2). \qquad (3)$$
Let $s = a + b + c + d$, $x_1 = s - 2d$, $x_2 = s - 2c$, $x_3 = s - 2b$, and $x_4 = s - 2a$. Then $x_1 = y + u$, $x_2 = v + x$, $x_3 = y - u$, $x_4 = v - x$. Because $a > b > c > d$, $x_1 > x_2 > x_3 > x_4$. Now (3) reads
$$x_1x_3 = 3x_2x_4. \qquad (4)$$
Because
$$xu + vy = (a - c)(b - d) + (a + c)(b + d) = 2(ab + cd)$$
and
$$x_1x_2 + x_3x_4 = (y + u)(v + x) + (y - u)(v - x) = 2(xu + yv),$$
we have
$$ab + cd = \frac{1}{4}(x_1x_2 + x_3x_4). \qquad (5)$$
Let $g = \gcd(x_1, x_4)$. It is clear that $s \equiv x_i \pmod 2$ for $i = 1, 2, 3, 4$. We consider the following cases.
(i) $s \equiv 1 \pmod 2$. First suppose that $g = 1$. Then by (4), there exists some positive integer $k$ such that $x_3 = kx_4$ and, consequently, $kx_1 = 3x_2$. Because $x_3 > x_4$, $k > 1$; because $x_1 > x_2$, $k < 3$. Therefore, $k = 2$. But then $x_3$ is even, contradicting the assumption that each $x_i$ is odd.
It follows that $g > 1$, and that $g$ divides $x_1x_2+x_3x_4 = 4(ab+cd)$.
Because $x_1$ and $x_4$ are odd, $g$ is odd as well, implying that $g \mid (ab+cd)$. Also observe that $x_1x_2+x_3x_4 \ge 3x_1+2x_4 \ge 3g+2g = 5g$, so that $g < ab+cd$. Therefore, $ab+cd$ is divisible by a number strictly between 1 and $ab+cd$, implying that it is composite.
(ii) $s \equiv x_i \equiv 0 \pmod{2}$. Let $x_i' = x_i/2$ for $i = 1, 2, 3, 4$, and let $g' = \gcd(x_1', x_2')$. Then $g = 2g' \ge 2$ and $x_1' > x_2' > x_3' > x_4'$. Note also that (4) and (5) become
$$x_1'x_3' = 3x_2'x_4' \quad \text{and} \quad ab + cd = x_1'x_2' + x_3x_4', \quad (4')$$
respectively.
If $g' > 1$, then $g' \mid (ab + cd)$. Since $ab + cd > x_2' \ge g'$, $ab + cd$ must be composite.
If $g' = 1$, then by (4'), $x_3' = kx_4'$ and $kx_1' = 3x_2'$ for some positive integer $k$. Then again by $x_3' > x_4'$ and $x_1' > x_2'$, $k = 2$. Hence 2 divides both $x_2'$ and $x_3'$ implying that $ab+cd$ is even (by (4')). Since $ab+cd > a > 2$, $ab+cd$ is composite.
From the above arguments, we conclude that $ab + cd$ is not prime.

Fourth Solution. (By Andrei Vorobiev, Russia) Let $x = b+d+a-c$. It is clear that $x > 1$. We have $c \equiv a+b+d \pmod x$ and $d \equiv c-a-b \pmod x$. These congruences, combined with the given condition, yield
$$\begin{aligned} 0 &\equiv ac + bd \equiv a(a + b + d) + bd \\ &\equiv (a + b)(a + d) \pmod x \end{aligned}$$
and
$$\begin{aligned} 0 &\equiv ac + bd \equiv ac + b(c - a - b) \\ &\equiv (a + b)(c - b) \pmod x. \end{aligned}$$
Hence, $x \mid (a+b)(a+d)$ and $x \mid (a+b)(c-b)$.
Because $a+b > (a+b) - (c-d) = x$ and $2x = 2[a + (b-c) + d] > 2a > a+b$, $a+b$ is not divisible by $x$. Thus, there is a prime $p$ that divides each of $x$, $(a+d)$, and $(c-b)$. To finish, we only need to prove that $p$ is a proper divisor of $ab+cd$. In fact, $ab+cd > a+d \ge p$ and
$$p \mid (a+d)b + (c-b)d = ab + cd,$$
as desired.

Fifth Solution. Let $ABCD$ be the quadrilateral with $AB = a, BC = d, CD = b, AD = c, \angle BAD = 60^\circ$, and $\angle BCD = 120^\circ$. Such a quadrilateral exists in view of (1) and the Law of Cosines; the common value in (1) is $BD^2$. Let $\angle ABC = \alpha$, so that $\angle CDA = 180^\circ - \alpha$. Applying the Law of Cosines to triangles $ABC$ and $ACD$ gives
$$a^2 + d^2 - 2ad \cos \alpha = AC^2 = b^2 + c^2 + 2bc \cos \alpha.$$
Hence, $2 \cos \alpha = (a^2 + d^2 - b^2 - c^2)/(ad + bc)$, and
$$AC^2 = a^2 + d^2 - ad \frac{a^2 + d^2 - b^2 - c^2}{ad + bc} = \frac{(ab + cd)(ac + bd)}{ad + bc}.$$
Because $ABCD$ is cyclic, the Ptolemy's Theorem yields
$$(AC \cdot BD)^2 = (AB \cdot CD + AD \cdot BD)^2 = (ab + cd)^2$$
It follows that
$$(ac + bd)(a^2 - ac + c^2) = (ab + cd)(ad + bc). \quad (6)$$
(Note that straightforward algebra can also be used to obtain (6) from (1).) Observe that
$$ab + cd > ac + bd > ad + bc. \quad (7)$$
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 (7) that $ab+cd$ and $ac+bd$ are relatively prime. Hence, from (6), it must be true that $ac+bd$ divides $ad+bc$. However, this is impossible by (7). Thus, $ab+cd$ must not be prime.

Sixth Solution. (By Reid Barton and Gabriel Carroll) Let $\omega = e^{\frac{2\pi i}{3}}$. Then
$$\omega^3 = 1 \quad \text{and} \quad 1 + \omega + \omega^2 = 0. \qquad (8)$$
We are going to use two fundamental facts about the ring $\mathbb{Z}[\omega]$:
* Fact 1. $\mathbb{Z}[\omega]$ is a unique factorization domain (UFD);
* Fact 2. the units in $\mathbb{Z}[\omega]$ are $\pm 1, \pm\omega, \pm\omega^2$.
Factoring (1) in $\mathbb{Z}[\omega]$ gives
$$(c + \omega a)(c + \omega^2 a) = (b - \omega d)(b - \omega^2 d). \qquad (9)$$
Lemma 1. If $a > b > c > d$ are positive integers satisfying (9), and $ab + cd$ is prime, then $c + \omega a$ and $b - \omega d$ are not relatively prime.
Proof. Assume for the sake of contradiction that $c + \omega a$ and $b - \omega d$ are relatively prime. Since complex conjugation is an automorphism of $\mathbb{Z}[\omega]$ sending $\omega$ to $\omega^2$, $c + \omega^2 a$ and $b - \omega^2 d$ must also be relatively prime. From the two facts, we conclude that $c + \omega a = u(b - \omega^2 d)$ for some unit $u \in \{\pm 1, \pm \omega, \pm \omega^2\}$.
If $u = \pm 1$, then $c + \omega a = \pm (b - \omega^2 d) = \pm (b + d) \pm \omega d$ (by the second part of (8)), contradicting $a \neq \pm d$.
If $u = \pm \omega$, then $c + \omega a = \pm \omega(b - \omega^2 d) = \mp d \pm \omega b$ (by the first part of (8), contradicting both $a \neq \pm b$ and $c \neq \mp d$).
If $u = \pm \omega^2$, then $c + \omega a = \pm \omega^2(b - \omega^2 d) = \pm(\omega^2 b - \omega d) = \mp b \mp (b+d)\omega$ (by (8)), contradicting $c \neq \mp b$.
In all cases, we reach a contradiction, so $c + \omega a$ and $b - \omega d$ are not relatively prime. ■
Lemma 2. If $a > b > c > d$ are positive integers satisfying (1) and $ab + cd$ is prime, then $ad = cb + cd$.
Proof. Since $a, b, c, d$ satisfy (1), they also satisfy (9), so by Lemma 1, there exists some prime $p = q + r\omega \in \mathbb{Z}[\omega]$ such that $p \mid c + \omega a$ and $p \mid b - \omega d$. Then $\overline{p} = q + r\omega^2 \mid b - \omega^2 d$, so $p\overline{p} \mid (c + \omega a)(b - \omega^2 d)$. Note that
$$N(p) = p\overline{p} = q^2 - qr + r^2$$
and that
$$(c + \omega a)(b - \omega^2 d) = bc + \omega ab - \omega^2 dc - \omega^3 ad \\ = (-ad + bc + dc) + (ab + cd)\omega.$$
Therefore, $N(p) \mid [(-ad + bc + dc) + (ab + cd)\omega]$. Since $N(p) \in \mathbb{Z}$, we must have $N(p) \mid (-ad + bc + dc)$ and $N(p) \mid ab + cd$. Since $ab + cd$ is prime, $N(p) = ab + cd$, and so $ab + cd \mid (-ad + bc + cd)$. But
$$ab + cd - (-ad + bc + dc) = (ab - bc) + ad > 0$$
and
$$ab + cd + (-ad + bc + dc) > ab - ad > 0,$$
so $|-ad+bc+cd| < ab+cd$. Hence, we must have $-ad+bc+cd = 0$, that is, $ad = cb + cd$.
Now suppose that $a > b > c > d > 0$ are integers satisfying (1). Then
$$\begin{aligned} (a-c)^2 + (a-c)c + c^2 &= a^2 - 2ac + c^2 + ac - c^2 + c^2 \\ &= a^2 - ac + c^2 \\ &= b^2 + bd + d^2. \end{aligned}$$
Since $c > d > 0$, we must have $a - c < b$ implying $(a - c)d < bd < bc$, or $ad < cb + cd$. By Lemma 2, $ab + cd$ cannot be prime, and we are done.