58-я Международная Математическая OлимпиадаБразилия, Рио-де-Жанейро, 2017 год

Упорядоченная пара $(x,y)$ целых чисел называется примитивной точкой, если наибольший общий делитель чисел $x$ и $y$ равен 1. Дано конечное множество $S$ примитивных точек. Докажите, что существуют натуральное $n$ и целые $a_0,$ $a_1,$ $\ldots,$ $a_n$ такие, что для каждой примитивной точки $(x,y)$ из $S$ выполнено равенство $$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.$$

Комментарий/решение

А где же само решение?

Если знаете решение, напишите, будем благодарны.

Решение: Докажем индукцией по $|S|.$

База. $|S|=1,$ по теореме Безу очевидно найдется искомый многочлен.

Переход. Пусть $S=\{(a_i,b_i)\mid i=1,...,m\}\cup \{a,b\}.$ По предположению индукции найдется искомый многочлен $g,$ что $g(a_i,b_i)=1.$

По Безу, пусть $Pa+Qb=1,$ где $P,Q$ целые.

Покажем, что найдутся $M\in \mathbb N, C\in \mathbb Z,$ что подойдет многочлен

$$ f(x,y)=g(x,y)^M+C(Px+Qy)^{M\cdot \deg g-m}\cdot \prod_{i=1}^{m}(b_ix-a_iy).$$

Очевидно $f$ однородный и $f(a_i,b_i)=1.$ Заметим, что

$$f(a,b)=g(a,b)^M+C\prod_{i=1}^{m}(b_ia-a_ib).$$

Достаточно показать, что $\gcd\Big(g(a,b),\prod_{i=1}^{m}(b_ia-a_ib)\Big)=1,$ а дальше легко добивается через Теорему Эйлера про $\varphi(n).$

Допустим простое $p\mid g(a,b),b_ia-a_ib$ для некоторого $i.$

$\bullet$ Если $p\mid b_ia\iff p\mid a_ib.$ БОО пусть $p\mid b,b_i.$ Раскрывая скобки у $g(a,b)$ и $g(a_i,b_i)=1$ легко получаем противоречие.

$\bullet$ Если $p\nmid a,b,a_i,b_i,$ то $\dfrac{a_i}{b_i}\equiv \dfrac{a}{b}\pmod p\implies 0\equiv g\left(\dfrac a b, 1\right)\equiv g\left(\dfrac{a_i}{b_i},1\right)\implies p\mid g(a_i,b_i)=1.$ Противоречие.