Найдите остаток от деления 6 в степени 100 на 7

Докажем, что 6^n при делении на 7 дает в остатке:

при нечетном n остаток 6,

при четном n остаток 1.

Доказательство проведем по индукции.

При n = 1:

6^1 = 6 = 7 * 0 + 6. Остаток 6.

При n = 2:

6^2 = 36 = 7 * 5 + 1. Остаток 1.

Пусть утверждение доказано для любого n < = N.

Рассмотрим

6^ (N + 1) = 6 * 6^N.

Если N - нечетное число, то 6^N = 7 * k + 6 и N + 1 - четное число. Тогда:

6 * 6^N = 6 * (7 * k + 6) = 7 * 6 * k + 36 = 7 * (6 * k + 5) + 1. Остаток при делении на 7 равен 1.

Если N - четное число, то 6^N = 7 * k + 1 и N + 1 - нечетное число. Тогда:

6 * 6^N = 6 * (7 * k + 1) = 7 * 6 * k + 6. Остаток при делении на 7 равен 6.

Утверждение доказано.

Из доказанного утверждения вытекает, что остаток от деления 6^100 на 7 равен 1,

так как 100 - четное число.