РЕШУ УРОК: задания, ответы, решения

Задания

Версия для печати и копирования в MS Word

Тип 26 № 7141 Добавить в вариант

Найти остаток от деления на 9 числа 23²⁷⁷.

Спрятать решение

Решение.

Число m  =  9 (наш делитель) является составным, и теорема Ферма не применима.

Если число A при делении на число m дает в остатке d, то $A в степени n левая круглая скобка mod m правая круглая скобка \equiv d в степени n левая круглая скобка mod m правая круглая скобка .$ У нас 23 при делении на 9 дает в остатке 5, поэтому $23 в степени левая круглая скобка 277 правая круглая скобка левая круглая скобка mod 9 правая круглая скобка \equiv5 в степени левая круглая скобка 277 правая круглая скобка левая круглая скобка mod 9 правая круглая скобка .$ Получаем:

$5 в степени левая круглая скобка 277 правая круглая скобка левая круглая скобка mod 9 правая круглая скобка \equiv5 умножить на левая круглая скобка 5 в кубе правая круглая скобка в степени левая круглая скобка 92 правая круглая скобка левая круглая скобка mod 9 правая круглая скобка \equiv5 умножить на 125 в степени левая круглая скобка 92 правая круглая скобка левая круглая скобка mod 9 правая круглая скобка \equiv5 умножить на 8 в степени левая круглая скобка 92 правая круглая скобка левая круглая скобка mod 9 правая круглая скобка \equiv5 умножить на 64 в степени левая круглая скобка 46 правая круглая скобка левая круглая скобка mod 9 правая круглая скобка \equiv5 умножить на 1 в степени левая круглая скобка 46 правая круглая скобка левая круглая скобка mod 9 правая круглая скобка \equiv 5 левая круглая скобка mod 9 правая круглая скобка .$

Ответ: 5.

Спрятать решение · Помощь