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

[nnosipov]

Кстати, а зачем Вам решать эту задачу? Для зачёта (условно говоря) или просто попалась случайно и захотелось решить?

[timber]

Задача является частью письменного экзамена при поступлении в Computer Science Center.

[Евгений Машеров]

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

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

(Оффтоп)

Разности нечётных чисел плачут - им запретили быть чётными...

[timber]

nnosipov в сообщении #946131 писал(а):

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

1. Допустим, что $2^n - 1$ делится на n, при n>1.
2. Пусть число p - простой делитель n, т.е. $n$\vdots$p$ (n делится на p).
3. Если $n$\vdots$p$, то $(2^n - 1)$\vdots$p$
4. p - нечетное число, $2^n - 1$ - нечетное.
5. Так как p - нечетное, то 2 не делится на p и следовательно $2^{p-1} - 1$\vdots$p$ (согласно МТФ).

Ну вот, пришел к МТФ. Что дальше делать, не понимаю?

[ИСН]

Откуда взялся пункт 3?

[timber]

ИСН в сообщении #947582 писал(а):

Откуда взялся пункт 3?

вывод из пунктов 2 и 1

[ИСН]

Ах, Вы так. Мда. Хм.
Нет, лучше как-то не так. Сейчас.

-- менее минуты назад --

Никто не предполагает, что $2^n - 1\vdots n$ для всех $n>1$. (Это слишком легко опровергнуть.) Может быть, хотя бы для некоторых? Но некоторые - это не все, вот и Ваше $p$ в них может входить, а может не входить, и делать вывод 3 из 1 и 2 нельзя.

[Null]

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

1. Допустим, что $2^n - 1$ делится на n, при n>1.
2. Пусть число p - простой делитель n, т.е. $n\vdots p$ (n делится на p).
3. Если $n\vdots p$, то $(2^n - 1)\vdots p$
4. p - нечетное число, $2^n - 1$ - нечетное.
5. Так как p - нечетное, то 2 не делится на p и следовательно $2^{p-1} - 1\vdotsp$ (согласно МТФ).

Тут все правильно. Я бы посоветовал рассмотреть для начала варианты $p=3,5,7$ может заметите что-нибудь.

[timber]

ИСН в сообщении #947589 писал(а):

Ах, Вы так. Мда. Хм.
Нет, лучше как-то не так. Сейчас.

-- менее минуты назад --

Никто не предполагает, что $2^n - 1\vdots n$ для всех $n>1$. (Это слишком легко опровергнуть.) Может быть, хотя бы для некоторых? Но некоторые - это не все, вот и Ваше $p$ в них может входить, а может не входить, и делать вывод 3 из 1 и 2 нельзя.

Делать выводы все таки можно, так как, если любое число $a$\vdots n$ и любое число $n$\vdots b$, то $a$\vdots b$ независимо от того какие числа a, b, n

-- 16.12.2014, 13:45 --

Null в сообщении #947596 писал(а):

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

1. Допустим, что $2^n - 1$ делится на n, при n>1.
2. Пусть число p - простой делитель n, т.е. $n\vdots p$ (n делится на p).
3. Если $n\vdots p$, то $(2^n - 1)\vdots p$
4. p - нечетное число, $2^n - 1$ - нечетное.
5. Так как p - нечетное, то 2 не делится на p и следовательно $2^{p-1} - 1\vdotsp$ (согласно МТФ).

Тут все правильно. Я бы посоветовал рассмотреть для начала варианты $p=3,5,7$ может заметите что-нибудь.

Рассматривать в применении к чему? К моему допущению 1) или к постановке задачи?

[ИСН]

А, ну да. Но это не очень перспективно. Ладно.
Смотрите вот так. Допустим, $2^n - 1\vdots n$, а $n\vdots3$, и значит, $2^n - 1\vdots3$. Что тогда можно сказать про $n$? Просто поставьте перед собой степени двойки и смотрите на них. Для каких $n$ будет $2^n - 1\vdots3$?

[nnosipov]

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

1. Допустим, что $2^n - 1$ делится на n, при n>1.
2. Пусть число p - простой делитель n, т.е. $n$\vdots$p$ (n делится на p).
3. Если $n$\vdots$p$, то $(2^n - 1)$\vdots$p$
4. p - нечетное число, $2^n - 1$ - нечетное.
5. Так как p - нечетное, то 2 не делится на p и следовательно $2^{p-1} - 1$\vdots$p$ (согласно МТФ).

Ну вот, пришел к МТФ. Что дальше делать, не понимаю?

Я бы посоветовал из двух делимостей $2^n-1 \vdots p$ и $2^{p-1}-1 \vdots p$ изготовить ещё одну делимость на $p$.

[whitefox]

Для четного $n$ доказательство очевидно.
Теперь рассмотрите не абы какой простой делитель $n,$ а наименьший.

[timber]

ИСН в сообщении #947606 писал(а):

А, ну да. Но это не очень перспективно. Ладно.
Смотрите вот так. Допустим, $2^n - 1\vdots n$, а $n\vdots3$, и значит, $2^n - 1\vdots3$. Что тогда можно сказать про $n$? Просто поставьте перед собой степени двойки и смотрите на них. Для каких $n$ будет $2^n - 1\vdots3$?

Для четных {$2n$, где $n$\in$N и n>1}

[ИСН]

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

Для четных

Верно! А может ли наше $n$ быть чётным, с учётом сделанных ранее предположений о делимости чего-то на что-то?

[timber]

Друзья, извините, немного отклонюсь от темы. Не кажется ли вам, что данная задача слишком сложно решается. Эта задача письменного экзамена (1 час). Причем это задача не в рамках какой-то всероссийской олимпиады по математике школьников или студентов мехматов. Мне кажется, что решение должно быть на раз, два ну может быть еще три. Но не так же. Я уже 3 дня думаю и изучаю основы теории чисел, а к решению прийти не могу. То решение, которое я привожу (доказательство от противного) уже содержит более 3 пунктов. Не уж-то все так сложно?!