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

14^256 mod 17 = (-3)^256 mod 17 = (3)^256 mod 17

Есть такая штука – т. Эйлера, по ней 3^16 mod 17 = 1

а 256 = 16*16. и сразу ответ : остаток единица.

У меня получилось 1. Привести ли выкладки?

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

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

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

ой