Найдите остатки от деления 14^256 на 17 ?

Answer 1

возьмем число А=14^256-1 и будем последовательно раскладывать разности квадратов, тогда получим А= (14^128 (14^64 (14^32 (14^16 (14^8 (14^4 (14^2 (14 (14-1) . мы разложили число А на множители в меньшей степени, деление некоторых из них на 17 легко проверить. (14-1) =13, не делится. (14=15, не делится. (14^2=197 не делится. (14^4=38417 не делится. (14^8=1475789057 делится! 1475789057/17=86811121. следовательно все число А делится на 17. заданное число 14^256=A, следовательно остаток при делении его на 17 равен 1. по первому ответу Lexovoy. раскладываем аналогично число В=3^256-1 и убеждаемся что (3^8=6562 делится на 17 (частное 386) и число 3^256 при делении на 17 дает остаток 1.

Answer 2

Рассмотрим остаток числа 14^2 по модулю 17. Это 9. Известно, что остаток степени числа по какому-то модулю равен остатку степени остатка этого числа по данному модулю. Это легко доказывается, но сейчас речь не об этом.
Осталась 128-я степень.
Остаток по модулю 17 квадрата получившегося числа (14^2) равен остатку 9^2, а это 16
Осталась 64-я степень
Остаток 14^4 равен остатку 16^2 а это 1
Все. 1 в любой степени 1, значит, при дальнейшем потенцировании числа каждый раз мы будем получать остаток 1.

В принципе, кроме использования леммы о степени остатка, доказательство похоже на доказательство Марата. Лемма позволила избежать вычислений с 10-значными числами.