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