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

Обозначим через $ \Bbb N $ множество всех целых положительных чисел. Упорядоченную пару $(a; b)$ чисел $a, b\in \Bbb N $ назовем интересной , если для любого $n\in \Bbb N $ существует $k\in \Bbb N $ такое, что число $a^k+b$ делится на $2^n$. Найдите все интересные упорядоченные пары чисел.

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

Ответы: любое $a > 1$ нечётное и $b$ такое, что $b \equiv -1, -a (mod 2^{\upsilon_2(a^2-1)})$. Для начала покажем, что $a$ и $b$ нечетные. Поскольку $a$ и $b$ одинаковой четности, скажем, $b=2^{b_0}\cdot t$, $t$ - нечетное, то при достаточно больших n, $\upsilon_2(a^{k}+b)=b_0$, что очевидно невозможно, значит $a, b$ нечетные.Заметим, что $a>1$.Рассмотрим фиксированное число k такое, что $2^k>a$ Пусть $c=ord_{2^k}(a)$, легкое применение $LTE $ даст нам, что $c=2^{k+1-\upsilon_2(a^2-1)}$.Рассмотрим множество чисел $N= \{a, a^2, ..., a^{2^{k+1-\upsilon_2(a^2-1)}\}}$, легко заметить, что по модулю $2^{\upsilon_2(a^2-1)}$ каждое число из этого множества дает остатки: либо $1$ либо $a$. Всего количество элементов в этом множестве - $2^{k+1-\upsilon_2(a^2-1)}$. Теперь рассмотрим множество $M = \{s|1\leq s\leq 2^k, s \equiv 1,$ или $a (mod 2^{\upsilon_2(a^2-1)})% }$, его количество элементом - $2^{k+1-\upsilon_2(a^2-1)}$. Но тогда число в $N$, тогда и только тогда когда это число сравнимо с $1$ или $a$ $(mod 2^{\upsilon_2(a^2-1)})$. Поэтому достаточно того, что $b \equiv -1, -a (mod 2^{\upsilon_2(a^2-1)})$.