Республиканская олимпиада по математике, 2017 год, 10 класс

Найдите все пары нечетных натуральных чисел $\left( a,b \right)$ таких, что $a,b < {{2}^{2017}}$, а числа ${{a}^{b}}+b$ и ${{b}^{a}}+a$ делятся на ${{2}^{2017}}$. ( Сатылханов К. )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. $\left( a,b \right)=\left( {{2}^{2017}}-1,1 \right)$, $\left( {{1,2}^{2017}}-1 \right)$, $\left( {{2}^{2016}}+{{1,2}^{2016}}-1 \right)$, $\left( {{2}^{2016}}-{{1,2}^{2016}}+1 \right)$.
Решение. Для каждого целого $n$ пусть ${{v}_{2}}\left( n \right)$ наибольшее целое число $k$ такое, что $n\vdots {{2}^{k}}$. В решении будем использовать следующую известную теорему:
Теорема (LTE): Если $a$ нечетно и $n$ четно, то $${{v}_{2}}\left( {{a}^{n}}-1 \right)={{v}_{2}}\left( a-1 \right)+{{v}_{2}}\left( a+1 \right)+{{v}_{2}}\left( n \right)-1.$$
Пусть для удобства $n=2017$. Если $b=1$, то $a+1\vdots {{2}^{n}}$, тогда $a={{2}^{n}}-1$. Аналогично, если $a=1$ то $b={{2}^{n}}-1$. Пусть теперь $a,b > 1$ и $s=a+b$. Так как ${{a}^{b}}-a=a\left( {{a}^{b-1}}-1 \right)\vdots {{a}^{2}}-1\vdots 4$, то $$s = {a^b} + b - \left( {{a^b} - a} \right) \vdots 4.$$ Без ограничения общности $a-1\vdots 4$ и $b+1\vdots 4$, то есть $$a-1={{2}^{k}}A, \ b+1={{2}^{m}}B,$$ где $k$, $m\ge 2$, $A$, $B$ — нечетные числа. По LTE $${{v}_{2}}\left( {{a}^{b-1}}-1 \right)={{v}_{2}}\left( a-1 \right)+{{v}_{2}}\left( a+1 \right)+{{v}_{2}}\left( b-1 \right)-1=$$ $$=k+1+1-1=k+1$$ и $${{v}_{2}}\left( {{b}^{a-1}}-1 \right)={{v}_{2}}\left( b-1 \right)+{{v}_{2}}\left( b+1 \right)+{{v}_{2}}\left( a-1 \right)-1=$$ $$=1+m+k-1=k+m.$$
Значит, ${{a}^{b}}-a={{2}^{k+1}}x,{{b}^{a}}-b={{2}^{k+m}}y$, где $x$ и $y$ нечетные числа. Тогда по условию ${{2}^{k+1}}x+s\vdots {{2}^{n}}$ и ${{2}^{k+m}}y+s\vdots {{2}^{n}}$. $a={{2}^{k}}A+1 < {{2}^{n}}\Rightarrow k\le n-1\Rightarrow {{2}^{k+1}}x+s\vdots {{2}^{n}}\vdots {{2}^{k+1}}\Rightarrow s\vdots {{2}^{k+1}}$. Если ${{v}_{2}}\left( s \right) > k+1$, то $n\le {{v}_{2}}\left( {{2}^{k+1}}x+s \right)=k+1$. Если ${{v}_{2}}\left( s \right)=k+1$, так как $m\ge 2$, то $n\le {{v}_{2}}\left( {{2}^{k+m}}y+s \right)={{v}_{2}}\left( s \right)=k+1$. В обоих случаях получаем $k=n-1\Rightarrow a={{2}^{n-1}}A+1 < {{2}^{n}}\Rightarrow A=1,a={{2}^{n-1}}+1$ и $s\vdots {{2}^{k+1}}\vdots {{2}^{n}}\Rightarrow {{2}^{n}}\le s=a+b < {{2}^{n+1}}\Rightarrow b={{2}^{n}}-a={{2}^{n-1}}-1.$

Заметим,что $a\not \equiv b(\bmod 4)$, так как в обратном случае $a^b+b\equiv 2(\bmod 4)$, что неверно.

Легко получить, что $a^{ab-1}\equiv b^{ab-1}\equiv 1(\bmod 2^{2017})$.

Так как $ab-1\equiv 2(\bmod 4)$, получаем, что $a^2\equiv b^2\equiv 1(\bmod 2^{2017})$.

Поэтому $a,b\in \{1,2^{2017}-1,2^{2016}-1,2^{2016}+1\}$.

Откуда $(a,b)=(1,2^{2017}-1)(2^{2017}-1,1)(2^{2016}-1,2^{2016}+1)(2^{2016}+1,2^{2016}-1)$.

Лемма:Для $\forall x,y \in\mathbb N$ таких, что $2\nmid x,y$ верно $$v_2(x^y+1)=v_2(x+1)$$

Доказательство леммы: $$x^y+1=(x+1)(x^{y-1}+x^{y-2}+...+x+1)$$

но в силу того, что вторая скобка нечётное число получаем, что утверждение леммы верно.

Заметим,что $a=1 \iff b=2^{2017}-1$ и $b=1 \iff a=2^{2017}-1$.

Далее будем считать что $1<a,b<2^{2017}-1$

Заметим, что $$v_2((a^b+1)+(b-1))\geq 2017$$

но из леммы $$0<v_2(a^b+1)=v_2(a+1)<2017$$ так же заметим, что $$0<v_2(b-1)<2017$$ откуда получаем $$v_2(a+1)=v_2(b-1)=k<2017$$ аналогично получаем $$v_2(b+1)=v_2(a-1)$$

Следовательно $a=2^ka_1-1$ и $b=2^kb_1+1$,где $2\nmid a_1,b_1$

Без ограничения общности примем, что $k\geq 2$.

Если $2\leq k\leq 2015$, то $2^{k+2}\mid 2^{2017}$, тогда

$a^b+b=(2^ka_1-1)^b+(2^kb_1+1)\equiv (b×2^ka_1-1)+(2^kb_1+1)=2^k(ba_1+b_1)\pmod {2^{k+2}}$

откуда $4\mid ba_1+b_1$, значит $4\mid a_1+b_1$

Так же заметим, что

$b^a+a=(2^kb_1+1)^a+(2^ka_1-1)\equiv (a×2^kb_1+1)+(2^ka_1-1)=2^k(ab_1+a_1)\pmod {2^{k+2}}$

откуда $4\mid ab_1+a_1$, значит $4\mid -b_1+a_1$,но тогда $4\mid 2a_1 \iff 2\mid a_1$, противоречие.Значит $k=2016$, откуда легко вывести, что $(a,b)=(2^{2016}+1,2^{2016}-1)$