Разделы 
Дополнительно
Задача по математике - 1074
2015-02-22 
а) Найдите все целые положительные $n$, для которых число $2^{n}-1$ делится на 7.
б) Докажите, что ни при каком целом положительном $n$ число $2^{n}+1$ не делится на 7.
Решение:
а) Пусть $n$ кратно трем. Тогда $n$ можно представить в виде $n=3k$ и $2^{n}-1 = 2^{3k}-1=8^{k} -1$. Но разность степеней с одинаковыми показателями делится на разность оснований, т. е. $8^{k}-1$ делится на $8-1=7$. Следовательно, $2^{n}-1$ делится на 7 при $n$, кратном 3.
Пусть $n$ некратно трем, $n=3k+1$ или $n=3k+2$. В случае $n=3k+1$ имеем $2^{n}-1=2^{3k+1}-1=2(8)^{k} -1 = 2 \cdot (7+1)^{k} - 1$, но $(7+1)^{k}$ при делении на 7 дает в остатке 1 (это следует, например, из формулы бинома Ныотона), $2(7+1)^{k}$ при делении на 7 даст в остатке 2. Значит, при делении $2^{n}-1=2(7+1)^{k}-1$ на 7 получится в остатке 1, следовательно, при $n=3k+1$ число $2^{n}-1$ не делится на 7.
В случае $n=3k+2$ имеем $2^{n}-1=2^{3k+2}-1=4(7+1)^{k}-1$. При делении на 7 получится в остатке 3.
Следовательно, $2^{n}-1$ делится на 7 тогда и только тогда, когда $n$ кратно трем.
б) Пусть $n=3k$. Тогда $2^{n} = 2^{3k} = 7m +1; 2^{n} + 1 =7m+2$, что не делится на 7.
Пусть $n=3k+1$, тогда $2^{n}+1 = 2^{3k+1} + 1 = 2 \cdot 2^{3k} + 1 = 2 (7m+1) + 1 = 14m+3$, что не делится на 7.
При $n=3k+2$ имеем $2^{n}+1 = 2^{3k+2} + 1 = 4 \cdot 2^{3k} + 1 = 4 (7m+1)+1=28m+5$, что также не делится на 7. Таким образом, ни при каком $n$ число $2^{n}+1$ не делится на 7.
Вариант решения.
Пусть $2^{k}$ дает при делении на 7 остаток $a_{k}$. Какой остаток $a_{k+1}$ даст $2^{k+1}$? Очевидно, надо $a$ умножить на 2 и вычесть 7, если $2a \geq 7$. Итак:
если $a_{k}=1$, то $a_{k+1} = 2$,
если $a_{k}=2$, то $a_{k+1} = 4$,
если $a_{k}=4$, то $a_{k+1} = 1$.
Остальные случаи можно не разбирать. Уже ясно, что последовательность остатков $2^{n}$ при делении на 7 такова: 1, 2, 4, 1, 2, 4, ... .
Отсюда без труда получаем решение задачи.
а) Найдите все целые положительные $n$, для которых число $2^{n}-1$ делится на 7.
б) Докажите, что ни при каком целом положительном $n$ число $2^{n}+1$ не делится на 7.
Решение:
а) Пусть $n$ кратно трем. Тогда $n$ можно представить в виде $n=3k$ и $2^{n}-1 = 2^{3k}-1=8^{k} -1$. Но разность степеней с одинаковыми показателями делится на разность оснований, т. е. $8^{k}-1$ делится на $8-1=7$. Следовательно, $2^{n}-1$ делится на 7 при $n$, кратном 3.
Пусть $n$ некратно трем, $n=3k+1$ или $n=3k+2$. В случае $n=3k+1$ имеем $2^{n}-1=2^{3k+1}-1=2(8)^{k} -1 = 2 \cdot (7+1)^{k} - 1$, но $(7+1)^{k}$ при делении на 7 дает в остатке 1 (это следует, например, из формулы бинома Ныотона), $2(7+1)^{k}$ при делении на 7 даст в остатке 2. Значит, при делении $2^{n}-1=2(7+1)^{k}-1$ на 7 получится в остатке 1, следовательно, при $n=3k+1$ число $2^{n}-1$ не делится на 7.
В случае $n=3k+2$ имеем $2^{n}-1=2^{3k+2}-1=4(7+1)^{k}-1$. При делении на 7 получится в остатке 3.
Следовательно, $2^{n}-1$ делится на 7 тогда и только тогда, когда $n$ кратно трем.
б) Пусть $n=3k$. Тогда $2^{n} = 2^{3k} = 7m +1; 2^{n} + 1 =7m+2$, что не делится на 7.
Пусть $n=3k+1$, тогда $2^{n}+1 = 2^{3k+1} + 1 = 2 \cdot 2^{3k} + 1 = 2 (7m+1) + 1 = 14m+3$, что не делится на 7.
При $n=3k+2$ имеем $2^{n}+1 = 2^{3k+2} + 1 = 4 \cdot 2^{3k} + 1 = 4 (7m+1)+1=28m+5$, что также не делится на 7. Таким образом, ни при каком $n$ число $2^{n}+1$ не делится на 7.
Вариант решения.
Пусть $2^{k}$ дает при делении на 7 остаток $a_{k}$. Какой остаток $a_{k+1}$ даст $2^{k+1}$? Очевидно, надо $a$ умножить на 2 и вычесть 7, если $2a \geq 7$. Итак:
если $a_{k}=1$, то $a_{k+1} = 2$,
если $a_{k}=2$, то $a_{k+1} = 4$,
если $a_{k}=4$, то $a_{k+1} = 1$.
Остальные случаи можно не разбирать. Уже ясно, что последовательность остатков $2^{n}$ при делении на 7 такова: 1, 2, 4, 1, 2, 4, ... .
Отсюда без труда получаем решение задачи.
