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
0,0(0 оценок)
Полный доступ
Позволит учиться лучше и быстрее. Неограниченный доступ к базе и ответам от экспертов и ai-bota
Оформи подписку