2014 dxdy logo

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

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


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


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

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

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

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

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



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


20/12/10
8858
Да нет, не очевидно: нечётное вполне может делиться на нечётное.

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


23/01/07
3415
Новосибирск
Я имел в виду необходимую четность степени $2$.

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


20/12/10
8858
Тогда не понял, почему очевидно. Серпинский ссылается на Шинцеля, вряд ли они оба проглядели бы какое-то очевидное рассуждение.

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


18/05/06
13435
с Территории
timber в сообщении #949431 писал(а):
ИСН в сообщении #949416 писал(а):
Разве для всех простых $x$ у нас $2^x-1$ делится на $p$?

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

Разве для всех простых $x<p,\;2^x-1\vdots p$? Проверьте на каких-нибудь небольших примерах.

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


23/01/07
3415
Новосибирск
nnosipov
Выражение $(p_i-1)$ для каждого нечетного простого - четное, соответственно, их НОК тоже будет четным, следовательно, сравнение $2^x-1\equiv0\pmod {y}$, где $x$ - НОК выражений $p_i-1$ всех простых делителей числа $y$ , будет выполняться при четном $x$.

-- 19 дек 2014 19:38 --

Я понял, что не прав.

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


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


При рассмотрении $p \mid 2^x-1$ у меня получается такие последовательности (проверял для $x$ до 50):
1)При $p=2$, $x=21, 22, 23, ..., 27$.
2) $p=3$, $x=2, 4, 6, ..., 22, 23, 24, ..., 28$.
3) $p=5$, $x=4, 8, 12, ..., 20, 22, 23, ..., 28$.
4) $p=7$, $x=3, 6, 9, ..., 18, 23, 24, ..., 29$.
5) $p=11$, $x=10, 20, 24, 25, 26, ..., 30, 39, 40, ..., 43$.

Только не понимаю, для чего все это?

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


18/05/06
13435
с Территории
Для установления того, где наша с Вашей арифметика начинает различаться. И вот, пожалуйста: сразу результат.
timber в сообщении #949826 писал(а):
1)При $p=2$, $x=21, 22, 23, ..., 27$.
Вы действительно это хотели написать, да? Вы уверены? То есть $p=2$ является делителем $2^{21}-1$?

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


14/12/14
454
SPb
ИСН в сообщении #949829 писал(а):
Для установления того, где наша с Вашей арифметика начинает различаться. И вот, пожалуйста: сразу результат.
timber в сообщении #949826 писал(а):
1)При $p=2$, $x=21, 22, 23, ..., 27$.
Вы действительно это хотели написать, да? Вы уверены? То есть $p=2$ является делителем $2^{21}-1$?


Я ошибся в программе. Считаю на компьютере. В программе у меня числа округляются вверх.

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


18/05/06
13435
с Территории
Да, разумеется, я так и понял. Ждать исправленного результата?

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


14/12/14
454
SPb
ИСН в сообщении #949839 писал(а):
Да, разумеется, я так и понял. Ждать исправленного результата?


Да, сейчас исправлю, будет новый результат.

-- 20.12.2014, 14:05 --

timber в сообщении #949843 писал(а):
ИСН в сообщении #949839 писал(а):
Да, разумеется, я так и понял. Ждать исправленного результата?


Да, сейчас исправлю, будет новый результат.


При рассмотрении $p \mid 2^x-1$ получаются такие последовательности:
1) $p=3$, $x=2, 4, 6, ..., 48, 49, 50$.
2) $p=5$, $x=4, 8, 12, ..., 48, 49, 50$.
3) $p=7$, $x=3, 6, 9, ..., 48, 50$.
4) $p=11$, $x=10, 20, 30, ..., 50$.

В начале получаются арифметические прогрессии. Только вот какое-то странное поведение на концах 48, 49, 50 и 48, 50

Честно говоря я уже запутался. И что нам это дает для понимания того, что, если $2^\delta\equiv 1 \pmod{p}$, то $\delta\mid n$ в доказательстве Шинцеля?

Все-таки очень хотелось бы во всем разобраться. Детально.

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


18/05/06
13435
с Территории
Странное поведение на концах - это опять глюки округления, поверьте уж на слово.
Итак, если $3\mid2^x-1$, то что можно сказать про $x$? (Ну и аналогично для других простых).

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


19/12/10
1546
timber в сообщении #949843 писал(а):
Честно говоря я уже запутался. И что нам это дает для понимания того, что, если $2^\delta\equiv 1 \pmod{p}$, то $\delta\mid n$ в доказательстве Шинцеля?

Это, вообще-то, следует из теоремы Лагранжа. Но можете и сами доказать. Для чего нужно $n$ разделить на $\delta$ и посмотреь чему равен остаток.

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


20/12/10
8858
whitefox в сообщении #949867 писал(а):
Это, вообще-то, следует из теоремы Лагранжа.
Не понимаю, причём здесь Лагранж. Это ведь свойства порядка элемента, почти сразу вытекающее из определения.

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


14/12/14
454
SPb
ИСН в сообщении #949866 писал(а):
Странное поведение на концах - это опять глюки округления, поверьте уж на слово.
Итак, если $3\mid2^x-1$, то что можно сказать про $x$? (Ну и аналогично для других простых).


Что же сказать про $x$?

Ну, например, $x$ - четное. $x$ является членом арифметической прогрессии с шагом $d=p-1$ (для данного примера). $x$ не является делителем $p$.

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


19/12/10
1546
nnosipov в сообщении #949873 писал(а):
Не понимаю, причём здесь Лагранж. Это ведь свойства порядка элемента, почти сразу вытекающее из определения.

По теореме Лагранжа $\delta$ делит порядок группы $\varphi(p)=p-1$, так что Лагранж здесь действительно ни причём.

Лучше этим не заморачиваться, и доказать непосредственно, как отмечено выше.

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

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



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

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


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

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