Доказательство неделимости числа (2^n - 1) на n

[timber]

Здравствуйте!

Небходимо доказать, что $2^ n - 1$ не делится на n для целого n>1.

[provincialka]

Немного напоминает малую теорему Ферма, вам не кажется?

[timber]

Может быть. Но надо доказать.

[provincialka]

Да, собственно, малая теорема Ферма и есть доказательство. Или вам ее использовать нельзя?

[timber]

Скорее всего, нельзя.

Пробовал 1) методом индукции и 2) принципом делимости

[nnosipov]

Малая теорема Ферма здесь пригодится, но предварительно нужно будет ещё кое-что сделать.

[provincialka]

nnosipov, ну, есть ведь общий вариант, для произвольных $p$. Если я правильно поняла ваш намек.

[nnosipov]

timber в сообщении #946060 писал(а):

Пробовал 1) методом индукции и 2) принципом делимости

Здесь будет полезным принцип крайнего.

-- Вс дек 14, 2014 17:50:49 --

provincialka в сообщении #946063 писал(а):

nnosipov, ну, есть ведь общий вариант, для произвольных $p$.

Не понимаю Вас. Что за общий вариант? Обобщение этой задачи?

[timber]

Можно ли рассуждать так:

1) При $n = 2$, имеем $2^2 - 1 = 3$, 3 не делится на 2 без остатка, доказано. Пусть $n = k$ и $2^k - 1$ не делится на k.

[nnosipov]

timber в сообщении #946067 писал(а):

Можно ли рассуждать так: ...

Нет, индукция здесь не поможет.

[timber]

Есть еще признак делимости: разность двух чисел не делится на число n, если и вычитаемое и уменьшаемое не делится на n.

[nnosipov]

timber в сообщении #946072 писал(а):

Есть еще признак делимости: разность двух чисел не делится на число n, если и вычитаемое и уменьшаемое не делится на n.

Нет такого признака (не)делимости.

-- Вс дек 14, 2014 18:18:34 --

timber, начните всё-таки с Малой теоремы Ферма. Найдите её формулировку, узнайте доказательство. Потом можно будет вернуться к этой задаче (она не такая простая, как кажется на первый взгляд).

[timber]

Друзья, даже и не знаю. Как-то неочевидно. МТФ - это теорема о простых числах. В условии задачи числа могут быть и простые и составные.

[nnosipov]

Никто не говорит, что МТФ нужно применять в лоб. Просто она понадобится в процессе доказательства. Иными словами, сначала нужно подготовить почву для её применения.

[timber]

Ну, хотя .... Ну, хотя есть обобщение МТФ на случай составного числа - это теорема Эйлера.