2014 dxdy logo

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

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


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


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

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

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

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

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



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


12/08/10
1606
Вы еще не получили доказательства, когда вы поймете как задача решается, сможете записать достаточно короткое решение.

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


19/12/10
1546
Доказательство всего в три пункта, которые Вы уже фактически выполнили.

Для нечётных $n:$
  1. Допустим $2^n\equiv1\pmod n;$
  2. пусть $p$ наименьший простой делитель $n,$ тогда по МТФ $2^{p-1}\equiv1\pmod p;$
  3. следовательно . . . что невозможно.

Хинт:
nnosipov в сообщении #947617 писал(а):
Я бы посоветовал из двух делимостей $2^n-1 \vdots p$ и $2^{p-1}-1 \vdots p$ изготовить ещё одну делимость на $p$.
С уточнением: изготовить ещё одну делимость на $q\mid (p-1).$

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


20/12/10
8858
timber в сообщении #947633 писал(а):
Не кажется ли вам, что данная задача слишком сложно решается. Эта задача письменного экзамена (1 час). Причем это задача не в рамках какой-то всероссийской олимпиады по математике школьников или студентов мехматов.
Видите ли, эта задача слишком хорошо известна (возможно, в узких кругах, но тем не менее): см., например, задачу 25 в задачнике Серпинского "250 задач по элементарной теории чисел".
whitefox в сообщении #947645 писал(а):
С уточнением: изготовить ещё одну делимость на $q\mid (p-1).$
Я имел в виду следующее: если $p \mid 2^n-1$ и $p \mid 2^{p-1}-1$, то $p \mid 2^d-1$, где $d=\gcd{(n,p-1)}=1$ (при подходящем выборе $p$). Можно также (как у Серпинского) рассмотреть $\delta$ --- порядок двойки по модулю $p$ (и показать, что $\delta=1$).

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


19/12/10
1546

(nnosipov)

А я имел ввиду, что $q\mid \operatorname{ord}_p(2).$

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


20/12/10
8858

(Оффтоп)

whitefox, да, я понял.

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


14/12/14
454
SPb
nnosipov в сообщении #947663 писал(а):
timber в сообщении #947633 писал(а):
Не кажется ли вам, что данная задача слишком сложно решается. Эта задача письменного экзамена (1 час). Причем это задача не в рамках какой-то всероссийской олимпиады по математике школьников или студентов мехматов.
Видите ли, эта задача слишком хорошо известна (возможно, в узких кругах, но тем не менее): см., например, задачу 25 в задачнике Серпинского "250 задач по элементарной теории чисел".
whitefox в сообщении #947645 писал(а):
С уточнением: изготовить ещё одну делимость на $q\mid (p-1).$
Я имел в виду следующее: если $p \mid 2^n-1$ и $p \mid 2^{p-1}-1$, то $p \mid 2^d-1$, где $d=\gcd{(n,p-1)}=1$ (при подходящем выборе $p$). Можно также (как у Серпинского) рассмотреть $\delta$ --- порядок двойки по модулю $p$ (и показать, что $\delta=1$).


Не совсем понятно доказательство Шинцеля в задачнике Серпинского:
1) Почему, если $2^\delta\equiv 1 \pmod{p}$, делается вывод, что $\delta\mid n$.
2) Почему делается итоговый вывод: число $n$ имеет делитель $>1$ и $<p$, а значит, также и простой делитель с этим свойством, что противоречит определению числа $p$. Правильно ли я понимаю это так: $1 <\delta <p$, в свою очередь число $\delta$ должно делится на какое-то простое число, допустим $p_2$, но $p_2 < p$ не может быть, так как $p$ - наименьшее?

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


20/11/12
5728
 ! 
timber в сообщении #949382 писал(а):
$2^\delta\equiv1$ (mod p)
timber, замечание за неправильное оформление формул.
$a\equiv b \pmod{m}$.

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


18/05/06
13435
с Территории
2) Да, так.
1) А для каких вообще степеней двойки будет $p \mid 2^x-1$? Опишите их все.

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


12/09/10
1547
ИСН в сообщении #949392 писал(а):
1) А для каких вообще степеней двойки будет $p \mid 2^x-1$? Опишите их все.

Я бы задал вопрос более конкретно.
Если $\delta$ -порядок двойки по модулю $p$, то докажите, что $2^x\equiv 1 \pmod{p} \Leftrightarrow \delta\mid x$

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


14/12/14
454
SPb
Цитата:
1) А для каких вообще степеней двойки будет $p \mid 2^x-1$? Опишите их все.


Для всех простых степеней двойки $x\in N_p.

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


18/05/06
13435
с Территории
Что такое $N_p$?

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


14/12/14
454
SPb
ИСН в сообщении #949410 писал(а):
Что такое $N_p$?


Подмножество простых чисел множества натуральных чисел.

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


18/05/06
13435
с Территории
Разве для всех простых $x$ у нас $2^x-1$ делится на $p$?

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


14/12/14
454
SPb
ИСН в сообщении #949416 писал(а):
Разве для всех простых $x$ у нас $2^x-1$ делится на $p$?


при условии $x < p$

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


23/01/07
3415
Новосибирск
whitefox в сообщении #947618 писал(а):
Для четного $n$ доказательство очевидно.

Для нечетного, с учетом необходимой четности степени двойки, на мой взгляд, тоже очевидно. Или я ошибаюсь?

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

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



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

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


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

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