IMO 1983 · Problem 3

Let \(a\), \(b\) and \(c\) be positive integers, no two of which have a common divisor greater than 1. Show that \(2abc-ab-bc-ca\) is the largest integer which cannot be expressed in the form \(xbc+yca+zab\),where \(x\), \(y\) and \(z\) are non-negative integers.

Official text of the problem. Official problem paper (PDF)

Solution

Put \[ F=2abc-ab-bc-ca. \] We prove that \(F\) is not representable and that every integer greater than \(F\) is representable.

Suppose first that \[ F=xbc+yca+zab \] for non-negative integers \(x,y,z\). Reducing modulo \(a\) gives \[ xbc\equiv-bc\pmod a. \] Since \(\gcd(a,bc)=1\), we have \(a\mid x+1\). As \(x+1>0\), this implies \(x\ge a-1\). Similarly, \[ y\ge b-1,\qquad z\ge c-1. \] Consequently, \[ \begin{aligned} F=xbc+yca+zab &\ge(a-1)bc+(b-1)ca+(c-1)ab\\ &=3abc-ab-bc-ca\\ &=F+abc>F, \end{aligned} \] a contradiction.

Now let \(N>F\) be any integer. Since \(\gcd(a,bc)=1\), multiplication by \(bc\) permutes the residue classes modulo \(a\). Thus we can choose an integer \(x\) satisfying \[ 0\le x\le a-1,\qquad xbc\equiv N\pmod a. \] Similarly, choose an integer \(y\) satisfying \[ 0\le y\le b-1,\qquad yca\equiv N\pmod b. \] Then \(N-xbc-yca\) is divisible by both \(a\) and \(b\). Since \(\gcd(a,b)=1\), it is divisible by \(ab\), so \[ z=\frac{N-xbc-yca}{ab} \] is an integer. Moreover, \[ \begin{aligned} zab &=N-xbc-yca\\ &\ge N-(a-1)bc-(b-1)ca\\ &>F-(a-1)bc-(b-1)ca\\ &=-ab. \end{aligned} \] Hence \(z>-1\), and its integrality gives \(z\ge0\). Therefore \[ N=xbc+yca+zab \] is a representation with all three coefficients non-negative.

These arguments also apply when any of \(a,b,c\) equals \(1\): congruences modulo \(1\) are automatic, and the chosen residue in the range \(0\) to \(1-1\) is \(0\).

Thus \(F=2abc-ab-bc-ca\) is exactly the largest integer that cannot be expressed in the required form. \(\square\)

The solution was checked against John Scholes' IMO solution archive (Kalva).