2014 dxdy logo

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

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


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


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

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

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

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

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



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


18/05/06
13435
с Территории
timber в сообщении #949875 писал(а):
$x$ является членом арифметической прогрессии с шагом $d=p-1$ (для данного примера).
Верно. То самое, что надо. Почти. Только можно сказать конкретнее. А то, знаете, числа 1, 3, 5, 7... тоже являются членами арифметической прогрессии с тем же самым шагом... но есть нюанс.

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


14/12/14
454
SPb
ИСН в сообщении #949887 писал(а):
timber в сообщении #949875 писал(а):
$x$ является членом арифметической прогрессии с шагом $d=p-1$ (для данного примера).
Верно. То самое, что надо. Почти. Только можно сказать конкретнее. А то, знаете, числа 1, 3, 5, 7... тоже являются членами арифметической прогрессии с тем же самым шагом... но есть нюанс.


Первый член прогрессии $x_1=p-1$ и разность $d=p-1$.

Или нюанс другой?

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


18/05/06
13435
с Территории
Именно такой. А нельзя ли этот смысл выразить покороче, без слов "арифметическая прогрессия"?

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


03/10/06
826
Само собой, что $n$ - число составное и нечётное. Пусть $n = (n_0+1)n_1$, где $(n_0+1)$ простое число и значит $2^{n_0}$ делит это $(n_0+1)$. А если $2^n$ делит $n$, то оно делит и число $(n_0+1)$.
$(2^n - 1) = (2^{n_0}2^{n_0}...2^{n_0}2^m - 1) = (2^m - 1) \mod (n_0+1)$, где нечётное $m<n_0$ и то, что $2^m - 1$ не делит $(n_0+1)$, думаю что очевидно.

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


20/12/10
8858
yk2ru в сообщении #950013 писал(а):
где нечётное $m<n_0$ и то, что $2^m - 1$ не делит $n_0+1$, думаю что очевидно.
Т.е. $2^3-1$ на $7$ делиться не может?

Кстати, слово "делит" Вы регулярно употребляете в смысле "делится на". (Например, говорят: $3$ делит $6$; это то же самое, что $6$ делится на $3$.)

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


03/10/06
826
nnosipov в сообщении #950022 писал(а):
делиться не может?

Значит показалось.

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


14/12/14
454
SPb
ИСН в сообщении #949912 писал(а):
Именно такой. А нельзя ли этот смысл выразить покороче, без слов "арифметическая прогрессия"?


Получается так:
$x_n=x_1+(n-1)d=(p-1)+(n-1)(p-1)=(p-1)n$ $\Rightarrow$ $n\mid x_n

Таким образом, правильно ли я понимаю, что Шинцель в своем доказательстве по аналогии с вышеприведенным, исходя из того, что $2^\delta\equiv 1 \pmod{p}$, сразу делает вывод, что $\delta\mid n$. Но, почему он приводит это без доказательства? Ведь это не так очевидно.

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


20/12/10
8858
$p-1 \mid x_n$ --- вот правильный вывод. То есть, все они делятся на $p-1$.

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


14/12/14
454
SPb
nnosipov в сообщении #950050 писал(а):
$p-1 \mid x_n$ --- вот правильный вывод. То есть, все они делятся на $p-1$.


ну там не для всех $p$ будет $p-1$, например при $p=7$, $x_1=p-4$, соответственно для всех $p$ правильнее будет записать $x_n=(p-n_1)n$

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


20/12/10
8858
timber в сообщении #950038 писал(а):
Ведь это не так очевидно.
Это почти очевидно. Вот смотрите: $\delta$ --- это самое маленькое число, такое, что $2^\delta \equiv 1 \pmod{p}$. А $n$ --- это какое-то число, для которого $2^n \equiv 1 \pmod{p}$. Нужно увидеть, что $n$ кратно $\delta$. Для этого поделим $n$ на $\delta$ с остатком: $n=\delta q+r$, где $0 \leqslant r<\delta$. Осталось показать, что $r=0$. Сделайте это.

-- Вс дек 21, 2014 00:54:57 --

timber в сообщении #950055 писал(а):
ну там не для всех $p$ будет $p-1$
Да, не для всех.

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


18/05/06
13435
с Территории
timber в сообщении #950038 писал(а):
Ведь это не так очевидно.
Вам было очевидно, что $7\times7=49$, до первой собственноручной проверки? Вот и тут то же самое. Если насобачиться - то да, это очевидно.

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


14/12/14
454
SPb
timber в сообщении #950038 писал(а):
ИСН в сообщении #949912 писал(а):
Именно такой. А нельзя ли этот смысл выразить покороче, без слов "арифметическая прогрессия"?


Получается так:
$x_n=x_1+(n-1)d=(p-1)+(n-1)(p-1)=(p-1)n$ $\Rightarrow$ $n\mid x_n

Таким образом, правильно ли я понимаю, что Шинцель в своем доказательстве по аналогии с вышеприведенным, исходя из того, что $2^\delta\equiv 1 \pmod{p}$, сразу делает вывод, что $\delta\mid n$?

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


18/05/06
13435
с Территории
Да, так.

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


14/12/14
454
SPb
Вариант логики, предлагаемый выше nnosipov - это доказательство другим способом или одно и то же?

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


18/05/06
13435
с Территории
По-моему, одно и то же, но вообще не вникал. Да какая разница. Все правильные доказательства эквивалентны.

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

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



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

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


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

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