2014 dxdy logo

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

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




На страницу 1, 2  След.
 
 Разложение выражения на множители
Сообщение21.06.2015, 18:24 
Пытаюсь в общем виде найти разложение на множители выражения $\[{2^n} - 1\]$ .
Ясно, что если $\[n = {k_{_1}} \cdot {k_2} \cdot ... \cdot {k_s}\]$, то $\[{2^{{k_{_1}} \cdot {k_2} \cdot ... \cdot {k_s}}} - 1 = ({2^{{k_{_1}}}} - 1)({({2^{{k_{_1}}}})^{{k_2} \cdot ... \cdot {k_s}}} + {({2^{{k_{_1}}}})^{{k_2} \cdot ... \cdot {k_s} - 1}} + ... + {2^{{k_{_1}}}} + 1)\]$. Как действовать дальше? Понятно, что $\[{2^{{k_{_1}} \cdot {k_2} \cdot ... \cdot {k_s}}} - 1 = ({2^{{k_{_1}}}} - 1)({2^{{k_{_2}}}} - 1)...({2^{{k_s}}} - 1)(???)\]$, но как найти оставшуюся часть разложения?

 
 
 
 Re: Разложение выражения на множители
Сообщение21.06.2015, 18:44 
Аватара пользователя
Вам понятно неправильно.

-- менее минуты назад --

$4095=2^{12}-1 = (2^6 - 1)(2^2 - 1)(???)$?

-- менее минуты назад --

Если сделать правильно, то оставшаяся часть выражается через круговые многочлены от чего-то там.

 
 
 
 Re: Разложение выражения на множители
Сообщение21.06.2015, 18:53 
ИСН, мой вопрос в том, что должно быть в скобках вместо знаков вопроса.

-- 21.06.2015, 19:59 --

Вообще, всё это делается ради решения задачи: доказать, что из $\[(m,n) = 1\]$ следует $\[({2^m} - {1,2^n} - 1) = 1\]$ . Может быть для решения задачи не обязательно находить в общем виде это разложение? Пробуем доказать утверждение от противного. Предположим, что числа $\[{2^m} - 1\]$ и $\[{2^n} - 1\]$ не взаимно просты. Откуда следует, что в таком случае $\[m\]$ и $\[n\]$ также не взаимно просты?

 
 
 
 Re: Разложение выражения на множители
Сообщение21.06.2015, 18:59 
Аватара пользователя
Да, я понял, что Ваш вопрос в том, что должно быть в скобках вместо знаков вопроса, в общем случае. Найдите сначала, пожалуйста, именно это в частном случае - в том, который я привёл.

-- менее минуты назад --

А, то есть эту фишку Вы уже знаете. Ну ОК, тогда всё.

-- менее минуты назад --

Находить разложение в общем виде, конечно, не обязательно. Тем более, что найти всё равно не получится. Надо не так.
waxwing_slain в сообщении #1029391 писал(а):
Предположим, что числа $\[{2^m} - 1\]$ и $\[{2^n} - 1\]$ не взаимно просты. Откуда следует, что в таком случае $\[m\]$ и $\[n\]$ также не взаимно просты?

Предположим, что $m>n$. То есть попросту $m=n+k, k>0$. И как мы раньше предположили, числа $\[{2^m} - 1\]$ и $\[{2^n} - 1\]$ не взаимно просты. Умножим второе из них на $2^k$ и вычтем его из первого. Что получится?

 
 
 
 Re: Разложение выражения на множители
Сообщение21.06.2015, 19:15 
ИСН, получится $\[{2^k} - 1\]$

 
 
 
 Re: Разложение выражения на множители
Сообщение21.06.2015, 19:19 
Аватара пользователя
Так. А что можно сказать о взаимной (не)простоте между ним и $2^n-1$?

 
 
 
 Re: Разложение выражения на множители
Сообщение21.06.2015, 19:30 
waxwing_slain в сообщении #1029387 писал(а):
Пытаюсь в общем виде найти разложение на множители выражения $\[{2^n} - 1\]$ .
$2^n-1$ раскладывается в произведение круговых многочленов. Дальше специфических методов нет.

 
 
 
 Re: Разложение выражения на множители
Сообщение21.06.2015, 20:30 
ИСН, ответа на Ваш последний вопрос я не знаю. Но из $\[{2^{m - 1}} - ({2^n} - 1) \cdot {2^k} = {2^k} - 1\]$ следует $\[m = 1\]$. Это противоречит предположению, что $\[m > n\]$. Но здесь никак не используется взаимная непростота $\[{2^{m - 1}}\]$ и $\[{2^{n - 1}}\]$

 
 
 
 Re: Разложение выражения на множители
Сообщение21.06.2015, 20:44 
Аватара пользователя
waxwing_slain в сообщении #1029421 писал(а):
Но из $\[{2^{m - 1}} - ({2^n} - 1) \cdot {2^k} = {2^k} - 1\]$ следует $\[m = 1\]$.
Каким образом оно из него следует?
И да, здесь никак не используется взаимная непростота $2^m - 1$ и $2^n - 1$.
Отойдём ещё на шаг назад. Пусть у нас два целых числа, $a\text{ и }b$, про которые известно только то, что они не взаимно просты, т.е. имеют нетривиальный общий множитель. Что можно сказать про число $a+b$: может ли оно быть взаимно просто с каждым из них, или с одним нет, а с другим да, или какие ещё варианты?

 
 
 
 Re: Разложение выражения на множители
Сообщение21.06.2015, 20:56 
ИСН
Цитата:
Каким образом оно из него следует?

Беру свои слова назад, не следует. Я нашёл ошибку.

Цитата:
Пусть у нас два целых числа, $a\text{ и }b$, про которые известно только то, что они не взаимно просты, т.е. имеют нетривиальный общий множитель. Что можно сказать про число $a+b$: может ли оно быть взаимно просто с каждым из них, или с одним нет, а с другим да, или какие ещё варианты?
Оно не может быть взаимно просто ни с одним из них, потому что делится на их наибольший общий делитель.

 
 
 
 Re: Разложение выражения на множители
Сообщение21.06.2015, 21:25 
Аватара пользователя
А (тот же вопрос) про $a-b$?

 
 
 
 Re: Разложение выражения на множители
Сообщение21.06.2015, 21:55 
Тот же ответ. Оно делится на их наибольший общий делитель. Таким образом, $\[{2^k} - 1\]$ и $\[{2^n} - 1\]$ имеют нетривиальный общий делитель. Но что это говорит нам о взаимной (не)простоте $\[m\]$ и $\[n\]$?

 
 
 
 Re: Разложение выражения на множители
Сообщение21.06.2015, 22:15 
Аватара пользователя
Пока ничего, но опытный охотник уже заметил след зверя. Мы уменьшили $m$ на $n$, и получили тот же вопрос, который имели, только с другими числами. Понизим его таким же приёмом ещё раз, и ещё, если надо. Где мы остановимся?

 
 
 
 Re: Разложение выражения на множители
Сообщение21.06.2015, 23:11 
Возможны два варианта, либо мы остановимся, когда оба показателя станут равными 1 и тогда получится абсурд, либо остановимся когда оба показателя будут равны, но больше единицы. Обозначим значение этих показателей через $\[t\]$. Практические примеры показывают, что в таком случае наибольший общий делитель этих чисел и равен $\[{2^t} - 1\]$

 
 
 
 Re: Разложение выражения на множители
Сообщение21.06.2015, 23:38 
Аватара пользователя
Ну вот и всё. Если два показателя равны и больше 1, то они уж точно не взаимнопросты. Теперь с этим знанием возвращаемся той же дорогой назад: какие показатели у нас были до последнего понижения? были ли они взаимно просты?

 
 
 [ Сообщений: 16 ]  На страницу 1, 2  След.


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