2014 dxdy logo

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

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


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


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

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

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

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

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



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


14/12/14
454
SPb
Здравствуйте!

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

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


18/01/13
12044
Казань
Немного напоминает малую теорему Ферма, вам не кажется? :D

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


14/12/14
454
SPb
Может быть. Но надо доказать.

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


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

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


14/12/14
454
SPb
Скорее всего, нельзя.

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

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


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

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


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

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


20/12/10
8858
timber в сообщении #946060 писал(а):
Пробовал 1) методом индукции и 2) принципом делимости
Здесь будет полезным принцип крайнего.

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

provincialka в сообщении #946063 писал(а):
nnosipov, ну, есть ведь общий вариант, для произвольных $p$.
Не понимаю Вас. Что за общий вариант? Обобщение этой задачи?

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


14/12/14
454
SPb
Можно ли рассуждать так:

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

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


20/12/10
8858
timber в сообщении #946067 писал(а):
Можно ли рассуждать так: ...
Нет, индукция здесь не поможет.

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


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

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


20/12/10
8858
timber в сообщении #946072 писал(а):
Есть еще признак делимости: разность двух чисел не делится на число n, если и вычитаемое и уменьшаемое не делится на n.
Нет такого признака (не)делимости.

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

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

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


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

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


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

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


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

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

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



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

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


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

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