Question

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

Answer 1

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