Разложение выражения на множители

[waxwing_slain]

Пытаюсь в общем виде найти разложение на множители выражения $\[{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)(???)\]$, но как найти оставшуюся часть разложения?

[ИСН]

Вам понятно неправильно.

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

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

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

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

[waxwing_slain]

ИСН, мой вопрос в том, что должно быть в скобках вместо знаков вопроса.

-- 21.06.2015, 19:59 --

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

[ИСН]

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

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

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

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

Находить разложение в общем виде, конечно, не обязательно. Тем более, что найти всё равно не получится. Надо не так.

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$ и вычтем его из первого. Что получится?

[waxwing_slain]

ИСН, получится $\[{2^k} - 1\]$

[ИСН]

Так. А что можно сказать о взаимной (не)простоте между ним и $2^n-1$?

[Sonic86]

waxwing_slain в сообщении #1029387 писал(а):

Пытаюсь в общем виде найти разложение на множители выражения $\[{2^n} - 1\]$ .

$2^n-1$ раскладывается в произведение круговых многочленов. Дальше специфических методов нет.

[waxwing_slain]

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

[ИСН]

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$: может ли оно быть взаимно просто с каждым из них, или с одним нет, а с другим да, или какие ещё варианты?

[waxwing_slain]

ИСН

Цитата:

Каким образом оно из него следует?

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

Цитата:

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

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

[ИСН]

А (тот же вопрос) про $a-b$?

[waxwing_slain]

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

[ИСН]

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

[waxwing_slain]

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

[ИСН]

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