|
Докажите, что при любом нечетном n число 2^(n!) -1 делится на n . задан 28 Дек '13 22:49 
parol |
|
Один из способов доказательства такой: рассмотрим степени двойки $%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 
falcao Может я не прав, но разве какая-то есть разница, что находится в степени? 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
|