Разделы 
Дополнительно
Задача по математике - 813
2014-03-02 
Найдите остаток от деления #2^{n}# на 3.
Решение:
Вычислим остатки для нескольких первых значений #n.# Остаток от деления 2 на 3 равен 2. Остаток от деления #2^{2}# на 3 равен 1. Остаток от деления #2^{3}# на 3 равен 2. Методом индукции докажем, что остаток от деления #2^{n}# на 3 равен 2 для нечетных и 1 для четных #n.# Для #n = 1# наше утверждение справедливо. Предположим, что оно справедливо для #n.# Запишем #2^{n+1} = 2 \cdot 2^{n}# и воспользуемся правилами действия над остатками. Если #n# нечетно, то по индукционному предположению остаток от деления #2^{n}# на 3 равен 2. Тогда остаток от деления #2^{n+1}# на 3 равен остатку от деления #2 \cdot 2 = 4# на 3, т.е. 1. Если же #n# четно, то остаток от деления #2^{n}# на 3 равен 1. И тогда остаток от деления #2^{n+1}# на 3 равен #2 \cdot 1 = 2.#
Найдите остаток от деления #2^{n}# на 3.
Решение:
Вычислим остатки для нескольких первых значений #n.# Остаток от деления 2 на 3 равен 2. Остаток от деления #2^{2}# на 3 равен 1. Остаток от деления #2^{3}# на 3 равен 2. Методом индукции докажем, что остаток от деления #2^{n}# на 3 равен 2 для нечетных и 1 для четных #n.# Для #n = 1# наше утверждение справедливо. Предположим, что оно справедливо для #n.# Запишем #2^{n+1} = 2 \cdot 2^{n}# и воспользуемся правилами действия над остатками. Если #n# нечетно, то по индукционному предположению остаток от деления #2^{n}# на 3 равен 2. Тогда остаток от деления #2^{n+1}# на 3 равен остатку от деления #2 \cdot 2 = 4# на 3, т.е. 1. Если же #n# четно, то остаток от деления #2^{n}# на 3 равен 1. И тогда остаток от деления #2^{n+1}# на 3 равен #2 \cdot 1 = 2.#
