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 
Вы еще не получили доказательства, когда вы поймете как задача решается, сможете записать достаточно короткое решение.

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

Для нечётных $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 
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 
Аватара пользователя

(nnosipov)

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

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

(Оффтоп)

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

 
 
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение19.12.2014, 12:10 
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 
Аватара пользователя
 ! 
timber в сообщении #949382 писал(а):
$2^\delta\equiv1$ (mod p)
timber, замечание за неправильное оформление формул.
$a\equiv b \pmod{m}$.

 
 
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение19.12.2014, 12:26 
Аватара пользователя
2) Да, так.
1) А для каких вообще степеней двойки будет $p \mid 2^x-1$? Опишите их все.

 
 
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение19.12.2014, 12:58 
ИСН в сообщении #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 
Цитата:
1) А для каких вообще степеней двойки будет $p \mid 2^x-1$? Опишите их все.


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

 
 
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение19.12.2014, 13:06 
Аватара пользователя
Что такое $N_p$?

 
 
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение19.12.2014, 13:08 
ИСН в сообщении #949410 писал(а):
Что такое $N_p$?


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

 
 
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение19.12.2014, 13:24 
Аватара пользователя
Разве для всех простых $x$ у нас $2^x-1$ делится на $p$?

 
 
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение19.12.2014, 14:13 
ИСН в сообщении #949416 писал(а):
Разве для всех простых $x$ у нас $2^x-1$ делится на $p$?


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

 
 
 
 Re: Доказательство неделимости числа (2^n - 1) на n
Сообщение19.12.2014, 14:28 
whitefox в сообщении #947618 писал(а):
Для четного $n$ доказательство очевидно.

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

 
 
 [ Сообщений: 89 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group