7-ші халықаралық Жәутіков олимпиадасы, 2011 жыл

$\mathbb{N}$ арқылы натурал сандар жиынын белгілейік. Егер кез келген $n\in \mathbb{N}$ үшін $a^k+b$ саны $2^n$-не бөлінетіндей $k \in \mathbb{N}$ табылса, онда $a,b \in \mathbb{N}$ сандарының реттелген $(a;b)$ парын қызық дейміз. Сандардың барлық қызық парларын табыңдар.

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

Ответы: любое $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)})$.