2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение14.12.2014, 15:05 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение16.12.2014, 13:00 


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

 Профиль  
                  
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение16.12.2014, 13:09 
Заслуженный участник
Аватара пользователя


11/03/08
9904
Москва
timber в сообщении #946072 писал(а):
Есть еще признак делимости: разность двух чисел не делится на число n, если и вычитаемое и уменьшаемое не делится на n.


(Оффтоп)

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

 Профиль  
                  
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение16.12.2014, 13:22 


14/12/14
454
SPb
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$ (согласно МТФ).

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

 Профиль  
                  
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение16.12.2014, 13:24 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
Откуда взялся пункт 3?

 Профиль  
                  
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение16.12.2014, 13:29 


14/12/14
454
SPb
ИСН в сообщении #947582 писал(а):
Откуда взялся пункт 3?


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

 Профиль  
                  
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение16.12.2014, 13:30 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
Ах, Вы так. Мда. Хм.
Нет, лучше как-то не так. Сейчас.

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

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

 Профиль  
                  
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение16.12.2014, 13:38 
Заслуженный участник


12/08/10
1677
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$ может заметите что-нибудь.

 Профиль  
                  
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение16.12.2014, 13:41 


14/12/14
454
SPb
ИСН в сообщении #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) или к постановке задачи?

 Профиль  
                  
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение16.12.2014, 13:49 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение16.12.2014, 14:03 
Заслуженный участник


20/12/10
9061
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$.

 Профиль  
                  
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение16.12.2014, 14:03 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение16.12.2014, 14:07 


14/12/14
454
SPb
ИСН в сообщении #947606 писал(а):
А, ну да. Но это не очень перспективно. Ладно.
Смотрите вот так. Допустим, $2^n - 1\vdots n$, а $n\vdots3$, и значит, $2^n - 1\vdots3$. Что тогда можно сказать про $n$? Просто поставьте перед собой степени двойки и смотрите на них. Для каких $n$ будет $2^n - 1\vdots3$?


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

 Профиль  
                  
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение16.12.2014, 14:22 
Заслуженный участник
Аватара пользователя


18/05/06
13438
с Территории
timber в сообщении #947622 писал(а):
Для четных

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

 Профиль  
                  
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение16.12.2014, 14:25 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 89 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group