IMO 2017 · Problem 6

An ordered pair \((x, y)\) of integers is a primitive point if the greatest common divisor of \(x\) and \(y\) is \(1\). Given a finite set \(S\) of primitive points, prove that there exist a positive integer \(n\) and integers \(a_0, a_1, \ldots, a_n\) such that, for each \((x, y)\) in \(S\), we have: \[ a_0x^n+a_1x^{n-1}y+a_2x^{n-2}y^2+\cdots+a_{n-1}xy^{n-1}+a_ny^n=1. \]

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

Solution

We shall construct a homogeneous polynomial of positive even degree, with integer coefficients, which takes the value \(1\) at every point of \(S\). If \(S\) is empty, the polynomial \(X^2\) suffices, so assume \(S\) is nonempty.

First, two primitive points lying on the same line through the origin must be equal or opposite. Indeed, suppose \[ (x',y')=t(x,y). \] By Bézout’s identity, there are integers \(r,s\) with \(rx+sy=1\). Consequently, \[ t=rx'+sy'\in\mathbb Z, \] and then \[ 1=\gcd(x',y')=|t|\gcd(x,y)=|t|. \] Thus \(t=\pm1\).

Choose representatives \[ P_i=(x_i,y_i),\qquad 1\le i\le m, \] from the distinct lines through the origin containing points of \(S\). Every point of \(S\) is therefore some \(P_i\) or \(-P_i\). Since our polynomial will have even degree, it is enough to obtain value \(1\) at the representatives.

For each \(i\), define \[ Q_i(X,Y)=\prod_{\substack{1\le j\le m\\j\ne i}}(y_jX-x_jY), \qquad d_i=Q_i(x_i,y_i). \] Empty products are understood to be \(1\). The representatives lie on distinct lines, so every \(d_i\) is a nonzero integer. Moreover, \[ Q_i(P_j)=0\qquad(j\ne i). \] Set \[ M=2\prod_{i=1}^{m}|d_i|. \] In particular, each \(d_i\) divides \(M\).

We next construct a homogeneous polynomial that is congruent to \(1\) modulo \(M\) at every primitive point. Write the prime factorization as \[ M=\prod_{\nu=1}^{t}p_\nu^{e_\nu}. \] Choose a positive integer \(k\) such that \[ k\ge \max(m,e_1,\ldots,e_t) \quad\text{and}\quad \varphi(p_\nu^{e_\nu})\mid k \quad\text{for every }\nu, \] where \(\varphi\) is Euler’s totient function. Such a \(k\) exists by taking a sufficiently large common multiple.

Consider \[ B(X,Y)=X^{2k}+Y^{2k}-X^kY^k. \] Fix a primitive point \((x,y)\) and a prime power \(p_\nu^{e_\nu}\) in \(M\). For any integer \(z\), \[ z^k\equiv \begin{cases} 0\pmod{p_\nu^{e_\nu}},&p_\nu\mid z,\\ 1\pmod{p_\nu^{e_\nu}},&p_\nu\nmid z. \end{cases} \] The first case follows from \(k\ge e_\nu\), and the second from Euler’s theorem. Because \(x\) and \(y\) are coprime, their \(k\)-th powers are congruent to one of \[ (1,0),\quad (0,1),\quad (1,1) \] modulo \(p_\nu^{e_\nu}\). In each case, \[ x^{2k}+y^{2k}-x^ky^k\equiv1\pmod{p_\nu^{e_\nu}}. \] Since these prime powers are pairwise coprime, we conclude that \[ B(x,y)\equiv1\pmod M \] at every primitive point.

For each \(i\), Bézout’s identity also gives integers \(u_i,v_i\) such that \[ u_ix_i+v_iy_i=1. \] Put \(L_i(X,Y)=u_iX+v_iY\), so \(L_i(P_i)=1\). Since \(d_i\mid M\), the numbers \[ c_i=\frac{1-B(x_i,y_i)}{d_i} \] are integers.

Now define \[ F(X,Y)=B(X,Y)+ \sum_{i=1}^{m}c_iQ_i(X,Y)L_i(X,Y)^{\,2k-m+1}. \] The exponent is nonnegative because \(k\ge m\). Each summand has degree \[ (m-1)+(2k-m+1)=2k, \] so \(F\) is homogeneous of degree \(2k\) and has integer coefficients.

At \(P_j\), every term in the sum except the \(j\)-th vanishes. Hence \[ F(P_j)=B(P_j)+c_jd_j=1. \] Its degree is even, so \(F(-P_j)=F(P_j)=1\) as well. Thus \(F\) takes the value \(1\) everywhere on \(S\).

Finally, expanding \[ F(X,Y)=\sum_{r=0}^{2k}a_rX^{2k-r}Y^r \] gives the required integers \(a_0,\ldots,a_{2k}\), with the positive integer \(n=2k\). \(\square\)

The solution was checked against the official IMO shortlist solutions.