Processing math: 61%

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


x және y бүтін сандарының ең үлкен ортақ бөлгіші 1 болатын (x,y) жұптығы примитивті нүкте болсын. Примитивті нүктелерден құралған S шекті жиыны берілген. S-тің ішінен әрбір (x,y) үшін a0xn+a1xn1y+a2xn2y2++an1xyn1+anyn=1.
посмотреть в олимпиаде

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

  -1
7 года 4 месяца назад #

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

  -1
7 года 4 месяца назад #

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

пред. Правка 2   4
2 года 10 месяца назад #

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

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

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

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

Покажем, что найдутся MN,CZ, что подойдет многочлен

f(x,y)=g(x,y)M+C(Px+Qy)Mdeggmmi=1(bixaiy).

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

f(a,b)=g(a,b)M+Cmi=1(biaaib).

Достаточно показать, что gcd а дальше легко добивается через Теорему Эйлера про \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. Противоречие.