XII математическая олимпиада «Шелковый путь», 2013 год

Определите все пары натуральных чисел $m, n,$ удовлетворяющих равенству $(2^m + 1, 2^n + 1) = 2^{(m, n)} + 1. $ Здесь $(a, b)$ — это наибольший общий делитель чисел $a, b$. ( Д. Елиусизов )

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

Ответ: $(m,n)=(dx,dy),\forall d,x,y\in\mathbb N, 2\nmid x,2\nmid y, (x,y)=1.$

1. Пусть $(m,n)=d$, тогда $m=dx, n=dy$, где $x,y\in\mathbb N$ и $(x,y)=1$.

Так как $2^d+1\mid 2^{dx}+1$, то $$0\equiv (2^d)^x+1\equiv (-1)^x+1\pmod {2^d+1}$$

если $2\mid x\implies 2^d+1\mid 2$, что невозможно. Значит $2\nmid x,y$.

2.Теперь докажем, что любая пара вида $(m,n)=(dx,dy)$, где $d,x,y\in\mathbb N, (x,y)=1$ и $2\nmid x,y$ удовлетворяют условию задачи.

Допустим $2^d=a,$ теперь докажем, что $(a^x+1, a^y+1)=a+1,$

тогда если какое-то простое $2<p\mid a^x+1\mid a^{2x}-1$ и $p\mid a^y+1\mid a^{2y}-1,$

то $p\mid a^{(2x,2y)}-1=a^2-1=(a+1)(a-1),$ но очевидно, что $p\nmid a-1,$ иначе $p\mid 2,$ что неверно. Значит $p\mid a+1,$ но с другой стороны

$$a^x+1=(a+1) \left( \sum_{i=0}^{x-1}a^i\cdot (-1)^{i} \right)=(a+1)a_x,$$

заметим, что $a_x \equiv x\pmod {a+1},$ аналогично $a_y\equiv y\pmod {a+1},$

тогда $(a_x,a_y)=1,$ ведь иначе их общий простой делитель $p$, который очевидно делит $(a^x+1,a^y+1),$ будет делить $a+1,$ но тогда $p\mid x,y$ противоречие.

Значит $(a^x+1,a^y+1)=(a+1)\cdot(a_x,a_y)=a+1,$ то есть

$$(2^m+1,2^n+1)=2^d+1=2^{(m,n)}+1.$$