Найти остаток от деления a^m на b. a=30 m=40 b=83

Ecли число a при делении на число b дает остаток d, то справдливо равенство:

a=br+d

r - частное, d - остаток,

1≤d < b

Возводим равенство в степень n:

aⁿ = (br+d) ⁿ

Раскрывая бином, записанный справа, замечаем, что все слагаемые

кроме последнего содержат b (или b в какой-то степени и потому кратны b)

Остаток от деления aⁿ на b равен остатку от деления dⁿ на b.

30⁴⁰ = (30²) ²⁰ = (900) ²⁰ = (830+70) ²⁰

Остаток от деления 30⁴⁰ на 83 равен остатку от деления 70²⁰ на 83.

70²⁰ = (70²) ¹⁰ = (4900) ¹⁰ = (4897+3) ¹⁰

Остаток от деления 70²⁰ на 83 равен остатку от деления 3¹⁰ на 83.

3¹⁰ = (3⁵) ² = (243) ² = (166+77) ²

Остаток от деления 3¹⁰ на 83 равен остатку от деления 77² на 83.

77²=5893+36

Остаток от деления 77² на 83 равен 36.

О т в е т. 36