Найти натуральные числа

[Руст]

Найти все натуральные числа n, для которых: $n|(2^{n-1}+1).$

[vbn]

Вам известно решение этой задачи?

[Руст]

Да, и оно (решение) не сложное.

[vbn]

То что

$$n$$

— нечетное, очевидно.
Легко показать, что

$$n \ne 0 (mod \ 3)$$

.
Таким образом,

$$n$$

следует искать среди чисел вида

$$6t \pm 1$$

.
Не подскажете идею доказательства?

[Руст]

Решением является только n=1. Идея длказательства отсутствия других решений заключается в том, что для простых делителей числа n последовательно показывается, что они должны иметь вид $p=1(mod \ 2^k)$, k=1,2,3,...

[Руст]

Приведу полное решение. Очевидно, что n не может быть чётным числом. Пусть $n=1+2^km$, где m - нечётное число и пусть р произвольный простой делитель n. Тогда из условия $2^{2^km}=-1(mod \ p)$ получаем, что $p=1(mod \ 2^{k+1})$. От того, что это выполняется для любого простого делителя, получаем, что m - чётное, что противоречит первоначальному выбору.