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

Задания

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

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

Найти остаток от деления на 17 числа $2 в степени левая круглая скобка 367 правая круглая скобка плюс 43.$

Решение.

На основании малой теоремы Ферма $2 в степени левая круглая скобка 16 правая круглая скобка \equiv 1 левая круглая скобка mod 17 правая круглая скобка .$ Поскольку

$2 в степени левая круглая скобка 367 правая круглая скобка =2 в степени левая круглая скобка 15 правая круглая скобка умножить на левая круглая скобка 2 в степени левая круглая скобка 16 правая круглая скобка правая круглая скобка в степени левая круглая скобка 22 правая круглая скобка \equiv 2 в степени левая круглая скобка 15 правая круглая скобка умножить на 1 \equiv 2 в степени левая круглая скобка 10 правая круглая скобка умножить на 2 в степени 5 левая круглая скобка mod 17 правая круглая скобка .$

При делении 1024 на 17 получаем в остатке 4, при делении 32 на 17 получаем в остатке 15, а потому

$2 в степени левая круглая скобка 15 правая круглая скобка = 1024 умножить на 32\equiv 4 умножить на 15 \equiv9 левая круглая скобка mod 17 правая круглая скобка .$

Тогда

$2 в степени левая круглая скобка 367 правая круглая скобка плюс 43\equiv9 плюс 43 левая круглая скобка mod 17 правая круглая скобка \equiv 52 \equiv1 левая круглая скобка mod 17 правая круглая скобка .$

Ответ: 1.

Примечание.

Можно было бы записать $32\equiv минус 2 левая круглая скобка mod 17 правая круглая скобка ,$ откуда

$2 в степени левая круглая скобка 367 правая круглая скобка =1024 умножить на 32 умножить на левая круглая скобка 2 в степени левая круглая скобка 17 минус 1 правая круглая скобка правая круглая скобка в степени левая круглая скобка 22 правая круглая скобка \equiv4 умножить на левая круглая скобка минус 2 правая круглая скобка умножить на 1 \equiv минус 8 левая круглая скобка mod 17 правая круглая скобка .$

а тогда

$2 в степени левая круглая скобка 367 правая круглая скобка плюс 43\equiv минус 8 плюс 43 \equiv35 \equiv1 левая круглая скобка mod 17 правая круглая скобка .$

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