Difference between revisions of "2017 IMO Problems/Problem 6"

(Solution)
 
(One intermediate revision by one other user not shown)
Line 6: Line 6:
 
==Solution==
 
==Solution==
 
{{solution}}
 
{{solution}}
 +
 +
 +
The proof goes by induction in the number <math>n=|S|</math> of points of the set.
 +
The base case is trivial by Bézout's Theorem.
 +
Write <math>S =\{(a_1,b_1)., \ldots, (a_n,b_n), (a_{n_1},b_{n+1})\}</math> and let <math>g(x,y)</math> be a homogeneous polynomial of degree <math>\ell</math> such that <math>g(a_i,b_i)=1</math> for <math>1 \leq i \leq n</math> (by the induction hypothesis). We will construct a homogeneous polynomial <math>f(x,y)</math> of the form
 +
<cmath>
 +
f(x,y)=g(x,y)^k + \prod_{i=1}^n (b_ix - a_iy) \cdot h(x,y),</cmath>
 +
where <math>k</math> and <math>h(x,y)</math> will be chosen so that the conditions are fulfilled.
 +
Note that <math>f(a_i,b_i) = 1</math> for <math>1 \leq i \leq n</math>, so we need to ensure that <math>f</math> is a homogeneous polynomial and that <math>f(a_{n+1},b_{n+1}) = 1</math>. We need that
 +
<cmath>
 +
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}).
 +
</cmath>
 +
If <math>\gcd\left(\prod_{i=1}^n (b_ia_{n+1} - a_ib_{n+1}),g(a_{n+1},b_{n+1})\right) = 1</math>, we can use Euler-Fermat's Theorem to guarantee that <math>h(a_{n+1},b_{n+1})</math> is an integer. If not, there would be a prime <math>p</math> such that <math>p</math> divides <math>g(a_{n+1},b_{n+1})</math> and wlog <math>b_1a_{n+1}-a_1b_{n+1}</math>. Working modulo <math>p</math>, we have that
 +
<cmath>
 +
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.</cmath>
 +
Analogously, we have that <math>a_{n+1}^{\ell} \equiv 0</math>, which is a contradiction, because <math>(a_{n+1},b_{n+1})</math> is a primitive point.
 +
In order to finish, it's enough to prove that for any integer <math>d\ge 0</math> and any integer <math>M</math>, there is a homogeneous polynomial <math>T(x,y)</math> of degree <math>d</math> such that <math>T(a_{n+1},b_{n+1}) = M</math>. For this, just take <math>T(x,y) = M(\alpha x + \beta y)^d</math>, where <math>\alpha</math> and <math>\beta</math> are integers such that <math>\alpha a_{n+1} + \beta b_{n+1} = 1</math>.
  
 
==See Also==
 
==See Also==
  
{{IMO box|year=2017|num-b=5|after=Last Problem}
+
{{IMO box|year=2017|num-b=5|after=Last Problem}}

Latest revision as of 13:39, 4 December 2024

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

See Also

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