IMO 2017 Problem 6
The earlier normalization attempt failed because the separated values were arbitrary nonzero integers and not necessarily invertible.
Proposed by: -
Verified: yes
Verdicts: PASS + PASS
Solve time: 16m42s
Problem
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. $$
| 2017 IMO (Problems) • Resources | ||
| Preceded by 2016 IMO Problems | 1 • 2 • 3 • 4 • 5 • 6 | Followed by 2018 IMO Problems |
| All IMO Problems and Solutions |
Exploration
The earlier normalization attempt failed because the separated values were arbitrary nonzero integers and not necessarily invertible. A different construction is needed. The induction method avoids this problem by ensuring that the value at the new point can be corrected using a factor whose value is coprime to the existing value.
For the delicate divisibility claim, the dangerous statement is that a large power can force divisibility. Testing the false claim with $3^N\equiv0\pmod 2$ gives the values $3,9,27,81,243$ for $N=1,2,3,4,5$, all congruent to $1$ modulo $2$. Thus that mechanism cannot be used.
The corrected idea is to prove that a certain product and the current polynomial value are coprime. Then Euler's theorem gives a power of the current value that is congruent to $1$ modulo the product. This allows an integer correction term.
For the small sizes of the set, the base cases behave correctly. If the set has one point $(x,y)$, Bézout gives integers $u,v$ with $ux+vy=1$, and the polynomial $ux+vy$ works. For two or more points, the induction step only uses the same coprimality argument, so the number of points is the relevant parameter rather than a small exponent.
Problem Understanding
Let
$$S={(x_1,y_1),\ldots,(x_m,y_m)}$$
be a finite set of primitive points. We seek a homogeneous polynomial with integer coefficients that takes the value $1$ at every point of $S$.
The flawed argument separated points correctly, but it tried to divide by nonunit integers. The new proof will instead add one point at a time and preserve the value $1$ at the previous points.
Key Observations
Lemma 1. If $(x_i,y_i)$ and $(x_j,y_j)$ are distinct primitive points, then
$$x_i y_j-y_i x_j\neq0.$$
Proof. If the determinant were zero, then the two vectors would be rational multiples. Write
$$(x_j,y_j)=\frac pq(x_i,y_i)$$
with $p,q$ coprime positive integers after changing signs if needed. Since $(x_j,y_j)$ has integer coordinates, $q$ divides both coordinates of $(x_i,y_i)$. Because $(x_i,y_i)$ is primitive, $q=1$. The same argument with the inverse ratio gives $p=1$, so the two points are equal. This contradicts distinctness. Hence the determinant is nonzero. ∎
Lemma 2. Suppose a homogeneous polynomial $G$ of degree $d$ satisfies
$$G(x_i,y_i)=1$$
for primitive points $(x_i,y_i)$, $1\le i\le r$. If $(x_{r+1},y_{r+1})$ is another primitive point, then
$$\gcd\left(G(x_{r+1},y_{r+1}),\prod_{i=1}^r(x_i y_{r+1}-y_i x_{r+1})\right)=1.$$
Proof. Let
$$A=\prod_{i=1}^r(x_i y_{r+1}-y_i x_{r+1}).$$
Assume a prime $p$ divides both $G(x_{r+1},y_{r+1})$ and $A$. Then for some $i$,
$$x_i y_{r+1}-y_i x_{r+1}\equiv0\pmod p.$$
Thus
$$(x_{r+1},y_{r+1})\equiv t(x_i,y_i)\pmod p$$
for some residue $t$. Because $(x_i,y_i)$ is primitive, at least one of $x_i,y_i$ is not divisible by $p$.
If $x_i\not\equiv0\pmod p$, then by homogeneity,
$$G(x_{r+1},y_{r+1}) \equiv t^dG(x_i,y_i) \equiv t^d\pmod p.$$
Since the left side is divisible by $p$, we get $t\equiv0\pmod p$, and then both $x_{r+1}$ and $y_{r+1}$ are divisible by $p$, impossible.
The case $y_i\not\equiv0\pmod p$ is identical. Hence the greatest common divisor is $1$. ∎
Solution
We prove the statement by induction on the size of $S$.
For one primitive point $(x_1,y_1)$, Bézout's identity gives integers $u,v$ such that
$$ux_1+vy_1=1.$$
The homogeneous polynomial
$$P(x,y)=ux+vy$$
works.
Assume the result holds for every set of $r$ primitive points. Let
$$S={(x_1,y_1),\ldots,(x_r,y_r),(x_{r+1},y_{r+1})}.$$
By induction, there exists a homogeneous polynomial $G$ of degree $d$ with integer coefficients such that
$$G(x_i,y_i)=1$$
for $1\le i\le r$.
Set
$$z=G(x_{r+1},y_{r+1})$$
and
$$A(x,y)=\prod_{i=1}^{r}(x_i y-y_i x).$$
By Lemma 2,
$$\gcd(z,A(x_{r+1},y_{r+1}))=1.$$
Let
$$C=A(x_{r+1},y_{r+1}).$$
Since $z$ and $C$ are coprime, Euler's theorem gives a positive integer $k$ such that
$$z^k\equiv1\pmod C.$$
Choose $k$ large enough that $kd\ge r$. Then
$$M=\frac{1-z^k}{C}$$
is an integer.
By Bézout's identity, choose integers $a,b$ satisfying
$$ax_{r+1}+by_{r+1}=1.$$
The polynomial
$$T(x,y)=M(ax+by)^{kd-r}$$
is homogeneous of degree $kd-r$ and has integer coefficients. Therefore
$$A(x,y)T(x,y)$$
is homogeneous of degree $kd$.
Now define
$$F(x,y)=G(x,y)^k+A(x,y)T(x,y).$$
The two terms have the same degree, so $F$ is homogeneous of degree $kd$.
For $1\le i\le r$, the product $A(x_i,y_i)$ is zero because the factor corresponding to $i$ vanishes. Hence
$$F(x_i,y_i)=G(x_i,y_i)^k=1.$$
At the new point,
$$F(x_{r+1},y_{r+1}) =z^k+C\cdot M.$$
Using the definition of $M$,
$$z^k+C\cdot\frac{1-z^k}{C}=1.$$
Thus the new point also has value $1$.
The induction is complete, so a suitable homogeneous polynomial exists for every finite set of primitive points. Writing it as
$$F(x,y)=a_0x^n+a_1x^{n-1}y+\cdots+a_ny^n$$
gives the required integers.
This completes the proof.
∎
Verification of Key Steps
The earlier failure came from trying to force a nonzero integer value to become invertible. The corrected proof never requires an integer inverse of a value such as $G(x_{r+1},y_{r+1})$.
The only divisibility step is the use of Euler's theorem after proving coprimality. Lemma 2 rules out the common prime divisors that would obstruct this step. The proof checks both possibilities for the residue class of a primitive point, because at least one coordinate must be nonzero modulo the prime.
The degree is controlled because the correction term is multiplied by $(ax+by)^{kd-r}$, and the choice $kd\ge r$ guarantees that the exponent is nonnegative. The final polynomial is homogeneous because both summands have degree $kd$.
Alternative Approaches
Another way to view the argument is through interpolation on the projective line over the integers. The determinant factors separate the primitive points, while the induction step supplies the missing normalization by exploiting primitiveness.
A second approach uses a unimodular change of coordinates sending the new primitive point to $(1,0)$. After this transformation, the correction step becomes simpler because the value at the new point can be controlled by a single variable. The induction above avoids introducing a matrix and keeps the construction entirely in the original coordinates.