2017 IMO Problems/Problem 6

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.$

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it.

The proof goes by induction in the number $n=|S|$ of points of the set. The base case is trivial by Bézout's Theorem. Write $S =\{(a_1,b_1)., \ldots, (a_n,b_n), (a_{n_1},b_{n+1})\}$ and let $g(x,y)$ be a homogeneous polynomial of degree $\ell$ such that $g(a_i,b_i)=1$ for $1 \leq i \leq n$ (by the induction hypothesis). We will construct a homogeneous polynomial $f(x,y)$ of the form $f(x,y)=g(x,y)^k + \prod_{i=1}^n (b_ix - a_iy) \cdot h(x,y),$ where $k$ and $h(x,y)$ will be chosen so that the conditions are fulfilled. Note that $f(a_i,b_i) = 1$ for $1 \leq i \leq n$ , so we need to ensure that $f$ is a homogeneous polynomial and that $f(a_{n+1},b_{n+1}) = 1$ . We need that $1 = f(a_{n+1},b_{n+1}) = g(a_{n+1},b_{n+1})^k + \prod_{i=1}^n (b_ia_{n+1} - a_ib_{n+1})\cdot h(a_{n+1},b_{n+1}).$ If $\gcd\left(\prod_{i=1}^n (b_ia_{n+1} - a_ib_{n+1}),g(a_{n+1},b_{n+1})\right) = 1$ , we can use Euler-Fermat's Theorem to guarantee that $h(a_{n+1},b_{n+1})$ is an integer. If not, there would be a prime $p$ such that $p$ divides $g(a_{n+1},b_{n+1})$ and wlog $b_1a_{n+1}-a_1b_{n+1}$ . Working modulo $p$ , we have that $0 \equiv b_1^{\ell}g(a_{n+1},b_{n+1}) \equiv g(b_1a_{n+1},b_1b_{n+1})\equiv g(a_1b_{n+1},b_1b_{n+1}) \equiv b_{n+1}^{\ell}g(a_1,b_1) \equiv b_{n+1}^{\ell}\mod p.$ Analogously, we have that $a_{n+1}^{\ell} \equiv 0$ , which is a contradiction, because $(a_{n+1},b_{n+1})$ is a primitive point. In order to finish, it's enough to prove that for any integer $d\ge 0$ and any integer $M$ , there is a homogeneous polynomial $T(x,y)$ of degree $d$ such that $T(a_{n+1},b_{n+1}) = M$ . For this, just take $T(x,y) = M(\alpha x + \beta y)^d$ , where $\alpha$ and $\beta$ are integers such that $\alpha a_{n+1} + \beta b_{n+1} = 1$ .

2017 IMO (Problems) • Resources
Preceded by Problem 5	1 • 2 • 3 • 4 • 5 • 6	Followed by Last Problem
All IMO Problems and Solutions

Page

Toolbox

Search

2017 IMO Problems/Problem 6

Problem

Solution

See Also