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


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

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

  0
2020-07-20 04:32:36.0 #

Ответ: $(m,n)=(dx,dy),\forall d,x,y\in\mathbb N, 2\nmid x,2\nmid y, (x,y)=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$.

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

Заметим, что $2^d+1\mid (2^d)^x+1=2^m+1$ и $2^d+1\mid (2^d)^y+1=2^n+1$, так как $2\nmid x,y$.

Допустим $2^m+1$ и $2^n+1$ имеют общий простой делитель $p$, такое, что $(p,2^d+1)=1$.

Заметим, что $p\mid 2^{2m}-1$ и $p\mid 2^{2n}-1$.

Пусть $t-$ наименьшее натуральное число, такое, что $p\mid 2^t-1$,

тогда $t\mid 2m$ и $t\mid 2n\implies t\mid 2d\implies p\mid 2^{2d}-1=(2^d-1)(2^d+1)$, но так как $(p,2^d+1)$, то $p\mid 2^d-1$, тогда $$0\equiv 2^m+1=(2^d)^x+1\equiv 1^x+1\equiv 2\pmod p$$

откуда $p=2$, что невозможно, ведь $2\nmid 2^m+1$.

Значит $(2^m+1,2^n+1)=2^d+1=2^{(m,n)}+1$.