Докажите, что при любом нечетном n число 2^(n!) -1 делится на n .

задан 28 Дек '13 22:49

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

Один из способов доказательства такой: рассмотрим степени двойки $%2^0=1$%, $%2^1=2$%, ..., $%2^m$%, ... и так далее. Среди остатков от деления этих чисел на $%n$% неизбежны повторения. Рассмотрим самое первый повторившийся остаток. Пусть это произошло у $%2^k$% и $%2^l$%, где $%k < l$%. Тогда $%2^l-2^k$% делится на $%n$%. Ввиду нечётности $%n$% можно прийти к выводу, что $%2^{l-k}-1$% делится на $%n$%. Положим $%m=l-k$%. Среди чисел $%1$%, $%2$%, ..., $%2^{m-1}$% все остатки от деления на $%n$% различны, поэтому таких чисел не больше $%n$% -- ввиду того, что при делении на $%n$% возможно всего $%n$% остатков. В рассматриваемом списке $%m$% чисел, то есть из приведённого рассуждения следует, что при некотором натуральном $%m\le n$% число $%2^m-1$% делится на $%n$%. Осталось заметить, что $%n!$% делится на $%m$%, и тогда $%2^{n!}-1$% делится на $%2^m-1$%, так как $%a^s-1=(a-1)(a^{s-1}+\cdots+a+1)$% кратно $%a-1$%.

ссылка

отвечен 28 Дек '13 23:14

Может я не прав, но разве какая-то есть разница, что находится в степени? 2^k = 2 по любому модулю, т.е. можно просто сказать, что 2 будет сравнимо с нулем по четному модулю, и единицей по нечетному, нет?

(7 Ноя '16 17:19) Williams Wol...

@Williams Wol...: здесь есть решение, основанное на применение функции Эйлера, и оно намного короче. Но если этот материал считается изученным, то такое упражнение просто не стоит давать. Оно слишком очевидно, и при этом достаточно слабое. Поэтому я опирался на принцип Дирихле. А вообще-то здесь 2^{ф(n)}=1(mod n), где ф(n)<=n делит n!.

Что означает Ваша фраза "2^k=2 по любому модулю", я не понимаю. Если имелось в виду по тому же модулю k, то для составных чисел это неверно: 2^9-2=510 не делится на 9.

(7 Ноя '16 19:16) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×3,154
×2,777
×480
×57

задан
28 Дек '13 22:49

показан
691 раз

обновлен
7 Ноя '16 19:16

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

по почте:

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

по RSS:

Ответы

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

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