М1762. Две тысячи делителей

Задача из журнала «Квант» (2001 год, 4 выпуск)

Условие

Существует ли натуральное число $n$ такое, что $n$ имеет ровно $2000$ различных простых делителей и $2^n+1$ делится на $n$?

Решение

Докажем по индукции, что для любого натурального $k$ существует натуральное $n_k$, имеющее $k$ различных простых делителей, делящееся на $3$ и такое, что $2^{n_k}+1$ делится на $n_k$.

Для $k=1$ можно взять $n=3$. Пусть число $n_k=n$, кратное $3$, имеет $k$ различных простых делителей, причём $2^n+1$ делится на $n$.

Число $2^{3n}+1=\left(2^n+1\right)\left(2^{2n}-2n+1\right)$ делится на $3n$. Это следует из того, что $2^n+1$ делится на $n$, а
$$2^{2n}-2^n+1=\left(2^n-2\right)\left(2^n+1\right)+3\;\;\;(*)$$ делится на $3$ (поскольку при нечётном $n$ числа $2^n+1$ и $2^n-2$ делятся на $3$).

Далее, число $2^{2n}-2^n+1$ не делится на $9$, поскольку на $9$ делится произведение $\left(2^n-2\right)\left(2^n+1\right)$. Значит, поскольку $2^{2n}-2^n+1>3$ при $n>1$, то это число имеет при $n>1$ простой делитель $p>3$. Так как НОД $\left(2^n+1, 2^{2n}-2^n+1\right)=3$ (это тоже ясно из равенства $(*)$), то $p$ — не делитель $n$.

Из сказанного следует, что число $3pn$ имеет $k+1$ простой делитель, причём $2^{3pn}+1$ делится на $3pn$. Последнее следует, например из равенства
$$\left(2^{3n}\right)^p+1=\left(2^{3n}+1\right)\left(\left(2^{3n}\right)^{p-1}-\left(2^{3n}\right)^{p-2}+\cdots+1\right)$$

Для завершения решения достаточно положить $n_{k+1}=3pn=3pn_k$.

А.Егоров, В.Сендеров

М1476

Условие

Докажите, что не существует различных простых чисел 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

Пусть pq — простые числа, 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 нечетны).