Докажите утверждение: для любых $%m$% и $%n$% - натуральных число $%2^n-1$% делится на число $%(2^m-1)^2$% тогда и только тогда, когда $%n$% делиться на $%m\cdot(2^m-1)$%

задан 16 Июн '13 18:13

изменен 16 Июн '13 21:43

ASailyan's gravatar image


15.4k729

10|600 символов нужно символов осталось
3

Прежде всего, из условия, что $%2^n-1$% делится на $%2^m-1$%, следует, что $%n$% делится на $%m$%. Чтобы в этом убедиться, достаточно поделить $%n$% на $%m$% с остатком: $%n=mq+r$%; $%0\le r < m$%. Тогда $%2^n=(2^m)^q\cdot2^r$%, и коль скоро $%2^m$% при делении на $%2^m-1$% даёт в остатке $%1$%, то это же верно и для $%(2^m)^q$%, в результате чего оказывается, что не только $%2^n-1$%, но и $%2^r-1$% делится на $%2^m-1$%. Из условия $%r < m$% сразу ясно, что $%r=0$%, то есть $%n=mq$%.

Теперь можно записать $$2^n-1=(2^m)^q-1=(2^m-1)((2^m)^{q-1}+(2^m)^{q-2}+\cdots+2^m+1).$$ Делимость $%2^n-1$% на $%(2^m-1)^2$% равносильна делимости второго сомножителя на $%2^m-1$%. Заменяя в этом сомножителе $%2^m$% числом $%1$%, то есть остатком от деления на $%2^m-1$%, мы получаем вместо второго сомножителя сумму $%q$% единиц, которая также должна делиться на $%2^m-1$%. То же рассуждение работает и в обратную сторону. Отсюда $%n=mq$% делится на $%(2^m-1)^2$%.

Это рассуждение выглядело бы ещё проще, если излагать его на языке сравнений. Тогда мы бы сказали, что $%2^m\equiv1\pmod{2^m-1}$% с последующим возведением этого сравнения в степени.

ссылка

отвечен 16 Июн '13 18:33

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×578
×493

задан
16 Июн '13 18:13

показан
630 раз

обновлен
16 Июн '13 21:43

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru