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

Вопрос школьника по предмету Алгебра

Найти остаток от деления 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