Difference between revisions of "2017 IMO Problems/Problem 6"
(→See Also) |
(→Solution) |
||
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 of integers is a primitive point if the greatest common divisor of and is . Given a finite set of primitive points, prove that there exist a positive integer and integers such that, for each in , we have:
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 of points of the set.
The base case is trivial by Bézout's Theorem.
Write and let be a homogeneous polynomial of degree such that for (by the induction hypothesis). We will construct a homogeneous polynomial of the form
where and will be chosen so that the conditions are fulfilled.
Note that for , so we need to ensure that is a homogeneous polynomial and that . We need that
If , we can use Euler-Fermat's Theorem to guarantee that is an integer. If not, there would be a prime such that divides and wlog . Working modulo , we have that
Analogously, we have that , which is a contradiction, because is a primitive point.
In order to finish, it's enough to prove that for any integer and any integer , there is a homogeneous polynomial of degree such that . For this, just take , where and are integers such that .
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 |