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\ge 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(\mathrm{mod}p)$. By (1), $$b^2(b^2+bd+d^2)=b^2(a^2-ac+c^2)=(ab{)}^2-ab(bc)+b^2{c}^2.$$ It follows that $$\begin{array}{rl}{b}^2(b^2+bd+d^2)& \equiv (ab{)}^2-ab(bc)+b^2{c}^2\\ & \equiv (cd{)}^2+cd(bc)+b^2{c}^2\\ & \equiv c^2(b^2+bd+d^2)(\mathrm{mod}p),\end{array}$$ 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).(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{array}{rl}{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{array}$$ or $$y^2-u^2=3(v^2-x^2).(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_1{x}_3=3x_2{x}_4.(4)$$ Because $$xu+vy=(a-c)(b-d)+(a+c)(b+d)=2(ab+cd)$$ and $$x_1{x}_2+x_3{x}_4=(y+u)(v+x)+(y-u)(v-x)=2(xu+yv),$$ we have $$ab+cd=\frac{1}{4}(x_1{x}_2+x_3{x}_4).(5)$$ Let $g=\gcd (x_1,x_4)$. It is clear that $s\equiv x_i(\mathrm{mod}2)$ for $i=1,2,3,4$. We consider the following cases. (i) $s\equiv 1(\mathrm{mod}2)$. First suppose that $g=1$. Then by (4), there exists some positive integer $k$ such that $x_3=k{x}_4$ and, consequently, $k{x}_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_1{x}_2+x_3{x}_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_1{x}_2+x_3{x}_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(\mathrm{mod}2)$. Let $x_i^{\prime }=x_i/2$ for $i=1,2,3,4$, and let $g^{\prime }=\gcd (x_1^{\prime },x_2^{\prime })$. Then $g=2g^{\prime }\ge 2$ and $x_1^{\prime }>x_2^{\prime }>x_3^{\prime }>x_4^{\prime }$. Note also that (4) and (5) become $$x_1^{\prime }{x}_3^{\prime }=3x_2^{\prime }{x}_4^{\prime }\text{and}ab+cd=x_1^{\prime }{x}_2^{\prime }+x_3{x}_4^{\prime },(4^{\prime })$$ respectively. If $g^{\prime }>1$, then $g^{\prime }\mid (ab+cd)$. Since $ab+cd>x_2^{\prime }\ge g^{\prime }$, $ab+cd$ must be composite. If $g^{\prime }=1$, then by (4'), $x_3^{\prime }=k{x}_4^{\prime }$ and $k{x}_1^{\prime }=3x_2^{\prime }$ for some positive integer $k$. Then again by $x_3^{\prime }>x_4^{\prime }$ and $x_1^{\prime }>x_2^{\prime }$, $k=2$. Hence 2 divides both $x_2^{\prime }$ and $x_3^{\prime }$ 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(\mathrm{mod}x)$ and $d\equiv c-a-b(\mathrm{mod}x)$. These congruences, combined with the given condition, yield $$\begin{array}{rl}0& \equiv ac+bd\equiv a(a+b+d)+bd\\ & \equiv (a+b)(a+d)(\mathrm{mod}x)\end{array}$$ and $$\begin{array}{rl}0& \equiv ac+bd\equiv ac+b(c-a-b)\\ & \equiv (a+b)(c-b)(\mathrm{mod}x).\end{array}$$ 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 $B{D}^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 =A{C}^2=b^2+c^2+2bc\cos \alpha .$$ Hence, $2\cos \alpha =(a^2+d^2-b^2-c^2)/(ad+bc)$, and $$A{C}^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).(6)$$ (Note that straightforward algebra can also be used to obtain (6) from (1).) Observe that $$ab+cd>ac+bd>ad+bc.(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\text{and}1+\omega +{\omega }^2=0.(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).(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\ne \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\ne \pm b$ and $c\ne \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\ne \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 $$\begin{gathered} (c+\omega a)(b-{\omega }^{2}d)=bc+\omega ab-{\omega }^{2}dc-{\omega }^{3}ad \\ =(-ad+bc+dc)+(ab+cd)\omega . \end{gathered}$$ 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{array}{rl}(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{array}$$ 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.