21-я Международная Жаутыковская олимпиада по математике, 2025 год

Пару натуральных чисел $(x, y)$ назовем хорошей, если $x$ и $y$ не делятся друг на друга, а множества простых делителей $x$ и $y$ совпадают. Даны различные взаимно простые натуральные числа $a$ и $b$. Докажите, что существует бесконечно много натуральных $n$, для каждого из которых найдётся натуральное $m$ такое, что пара $(a^n+bm, b^n+am)$ хорошая. ( Сатылханов К. )

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

Возьмем $m' = m + \frac{a^n - b^n}{a-b}$, тогда наша пара преобразуется в $( \frac{a^{n+1} - b^{n+1}}{a-b} + am', \frac{a^{n+1} - b^{n+1}}{a-b} + bm' )$

Теперь, преобразовав $m'' = m'*\frac{a^{n+1} - b^{n+1}}{a-b}$ , получим: $(( \frac{a^{n+1} - b^{n+1}}{a-b})*(am'' +1), (\frac{a^{n+1} - b^{n+1}}{a-b})*(bm'' + 1))$

Лемма: Мы можем выбрать $m''$ так, чтобы 2 числа в паре друг на друга не делились.

Доказательство леммы: Не нарушая общности. возьмем $a>b$,тогда чтобы 2 числа в паре не делились, достаточно показать, что $(bm''+1)\nmid(am''+1)$. Аналогично достаточно показать, что $(bm''+1)\nmid m''(a-b)$, т.к. НОД$(bm''+1,m'')=1$, то мы должны выбрать такое $m''$, что$(bm''+1)\nmid (a-b)$, и любое достаточно большое $m''$ подходит. Лемма доказана.

Выбрав $m''$ по Лемме и выбрав $n=k\phi(am''+1)*\phi(bm''+1)-1$ для любого натурального $k$, получаем, что любой простой делитель, содержащийся в $am''+1$ или $bm''+1$, содержится в $\frac{a^{n+1} - b^{n+1}}{a-b}$ и т.к. эта дробь является множителем обоих чисел в паре, то и её простые делители будут делить оба числа.

Ч.Т.Д.