58-я Международная Математическая Oлимпиада
Бразилия, Рио-де-Жанейро, 2017 год
Комментарий/решение:
Решение: Докажем индукцией по |S|.
База. |S|=1, по теореме Безу очевидно найдется искомый многочлен.
Переход. Пусть S={(ai,bi)∣i=1,...,m}∪{a,b}. По предположению индукции найдется искомый многочлен g, что g(ai,bi)=1.
По Безу, пусть Pa+Qb=1, где P,Q целые.
Покажем, что найдутся M∈N,C∈Z, что подойдет многочлен
f(x,y)=g(x,y)M+C(Px+Qy)M⋅degg−m⋅m∏i=1(bix−aiy).
Очевидно f однородный и f(ai,bi)=1. Заметим, что
f(a,b)=g(a,b)M+Cm∏i=1(bia−aib).
Достаточно показать, что 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. Противоречие.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.