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


$x$ және $y$ бүтін сандарының ең үлкен ортақ бөлгіші 1 болатын $(x,y)$ жұптығы примитивті нүкте болсын. Примитивті нүктелерден құралған $S$ шекті жиыны берілген. $S$-тің ішінен әрбір $(x,y)$ үшін $$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.$$
посмотреть в олимпиаде

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

  -1
2017-12-23 21:48:59.0 #

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

  -1
2017-12-24 00:34:53.0 #

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

пред. Правка 2   4
2022-06-12 23:27:25.0 #

Решение: Докажем индукцией по $|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.$ Противоречие.