Ответ: $n=3$ — единственное нужное число.
Будем обозначать наибольший общий делитель целых чисел $a$, $b$ через $(a,b)$.
В решении постоянно будут использоваться такие леммы:
- Если $p$ — простое, то $2^{p-1}-1$ делится на $p$. Это — частный случай малой теоремы Ферма.
- Если $a$, $b$, $p$ — натуральные числа такие, что $2^a-1$ и $2^b-1$ делятся на $p$, то и $2^{(a,b)}-1$ делится на $p$.
Последнее утверждение мы докажем в конце решения.
Вернёмся к исходной задаче. Пусть $2^n+1$ делится на $n$, $p$ — наименьший простой делитель $n$ ($n$ и $p$ — нечётные числа, больше 1). Поскольку $2^{2n}-1=(2^n+1)(2^n-1)$ делится на $p$ и согласно (1) $2^{p-1}-1$ делится на $p$, а $(2n,p-1)=2$ (ведь любой простой делитель $2n$, кроме 2, больше $p$), в соответствии с (2) $2^2-1$ делится на $p$, т. е. $p=3$.
Положим $n=3m$. Если $m=1$, то $n=3$ и $2^n+1=9$ делится на $n^2=9$. Докажем, что случай $m\gt1$ невозможен.
Допустим сначала, что $m$ делится на 3, так что $n=3^kl$, $k\gt1$ и $(l,3)=1$. Если $2^n+1$ делится на $n^2$, то оно делится на $3^{2k}$. Разложим $2^n+1=(-1+3)^n+1$ по формуле бинома Ньютона и учтём, что $n$ нечётно:
$$
1+(-1+3)^n=1+(-1)^n+3n-3^2\,\dfrac{n(n-1)}2+\ldots+(-1)^{n-s}3^s\,\dfrac{n!}{s!}+\ldots+3^n.
$$
Отсюда видно, что $3n=3^{k+1}l$ делится на $3^{k+2}$. (Остальные члены $\dfrac{3^sn!}{s!}$ ($s\ge2$) делятся на $3^{k+2}$ поскольку степень 3, на которую делится $s!$, меньше $\dfrac s3+\dfrac s9+\dfrac{s}{27}+\ldots=\dfrac s2$, $n$ делится на $3^k$, и потому 3 входит с показателем большим $s-\dfrac s2+k=\dfrac s2+k\ge k+1$.) Но это противоречит тому, что $(l,3)=1$.
Пусть теперь $q$ — наименьший простой делитель $m$, $q\ge5$. Как и выше, используем (1) и (2). Поскольку $2^{2n}-1$ и $2^{q-1}-1$ делятся на $q$, $d=(2n,q-1)$ может равняться лишь 2 или 6 (ведь простые делители $n=3m$, кроме 3, больше $q$), причём $2^d-1$ делится на $q\ge5$. Остаётся рассмотреть случай $d=6$. Тогда $2^6-1=63$, $q=7$. Поскольку $2^3-1$ делится на 7, то $2^n-1=2^{3m}-1$ делится на 7, но тогда $2^n+1$ не делится на 7 и тем самым на $n$.
Осталось доказать лемму (2). Мы докажем эквивалентное утверждение:
$$
(2^a-1,2^b-1)=2^{(a,b)}-1.
$$
Вспомним, что наибольший общий делитель $(a,b)$ можно искать с помощью алгоритма Евклида: если $a\gt b$, то $$
(a,b)=(a-b,b),\tag{*}
$$
переходя с помощью шагов (*) к меньшим числам — меняя при надобности их местами, $(x,y)=(y,x)$ — мы приходим к паре $(d,0)$, где $d=(a,b)$.
Заметим теперь, что (при $a\gt b\gt1$)
$$
(2^a-1,2^b-1)=(2^a-2^b,2^b-1)=(2^b(2^{a-b}-1),2^b-1)=(2^{a-b}-1,2^b-1).\tag{**}
$$
В последнем равенстве используется, что число $2^k-1$ при $k\gt1$ нечётны. Таким образом, каждому шагу (*) соответствует шаг (**) и одновременно с парой $(d,0)$ в первой цепочке алгоритма Евклида мы получим пару $(2^d-1,2^0-1)=(2^d-1,0)$ во второй цепочке. Отсюда следует, что $$
(2^a-1,2^b-1)=2^d-1.
$$
