Условие

Докажите, что не существует различных простых чисел p, q таких, что $2^{p}+1$ делится на $q$, $2^{q}+1$ делится на $p$.

Доказательство

Ясно, что $p$ и $q$ нечетны, и если одно из них равно 3, то другое тоже должно равняться 3. Поэтому будем в дальнейшем считать, что $p>q>3$.

Первое решение.

Из условия следует, что $2^{2p}\equiv1(\bmod m)$.
С другой стороны, согласно малой теореме Ферма, для простого $q$ имеем: $2^{q-1}\equiv1(\bmod q)$.
Пусть n — найменьшее натуральное число такое, что $2^n=1(mod q)$. Тогда $n\neq 2$ — отличный от единицы делитель числа $2p$. Значит, $n=p$ либо $n=2p$, т.е. n не является делителем числа $q-1$. Противоречие.
Второе решение можно получить, опираясь на следующее утверждение.

Лемма 1

Пусть $p$, $q$ — простые числа, $q\neq 3$,$2^{p}+1$ делится на $q$. Тогда $q=2kp+1$, где $k$ — натуральное число. Эту лемму легко доказать, заметив, что число n в первом решении равно $2p$. Из нее следует, что $q>p$. Противоречие.
Еще одно решение можно получить, опираясь на такое утверждение.

Лемма 2

Если числа a и b взаимно просты, то НОД($2^{a}+1$, $2^{b}+1$)=1,

либо НОД($2^{a}+1$, $2^{b}+1$)=3
(причем второй случай имеет место тогда и только тогда, когда $a$ и $b$ нечетны).

Третье решение

Имеем:$2^{p}+1$ делится на $q$; $2^{q-1}-1$, по малой теореме Ферма, также делится на $q$. Следовательно, и $2^{p-q+1}+1$ делится на $q$ — в противоречии с леммой 2.

Замечание.

Лемма 2 является частным случаем следующего несложного утверждения. Пусть НОД($m$,$n$)=1, НОД($a$,$b$)=$d$, НОД($m^{a}+n^{a}$, $m^{b}+n^{b}$)=$d_{1}$. Тогда $d_{1}=m^{d}+n^{d}$, если числа $\frac{a}{d}$ и $\frac{b}{d}$ оба нечетны; $d_{1}=1$ либо $d_{1}=2$ в противном случае (а именно: $d_{1}=1$, если $m$ и $n$ разной четности; $d_{1}=2$, если $m$ и $n$ нечетны).