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

Задания

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

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

а)  Докажите, что 13¹⁶⁰ − 1 делится на 187.

б)  Докажите, что 300⁴⁸⁰ − 1 делится на 1001.

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

Решение.

Используем теорему Эйлера, которая утверждает, что для любого числа а и n таких, что а и n взаимно просты, выполняется: $\boldsymbola в степени левая круглая скобка фи левая круглая скобка n правая круглая скобка правая круглая скобка \equiv 1$ $\bmod n$ где $фи левая круглая скобка n правая круглая скобка$ - функция Эйлера, которая для простого числа p равна $р минус 1.$ В нашем случае $187=13 \times 14 плюс 1,$ поэтому $фи левая круглая скобка 187 правая круглая скобка =12$ (так как 13 и 14 взаимно просты). Таким образом: $13 в степени левая круглая скобка 12 правая круглая скобка \equiv 1 \bmod 187$ Теперь нам нужно найти $13 в степени левая круглая скобка 160 правая круглая скобка \bmod 187.$ Заметим, что: $160=12 \times$ 13 + 4 Следовательно: $13 в степени левая круглая скобка 160 правая круглая скобка =13 в степени левая круглая скобка 12 \times 13 плюс 4 правая круглая скобка = левая круглая скобка 13 в степени левая круглая скобка 12 правая круглая скобка правая круглая скобка в степени левая круглая скобка 13 правая круглая скобка \times 13 в степени 4 \equiv 1 в степени левая круглая скобка 13 правая круглая скобка \times 13 в степени 4 \equiv$ $13 в степени 4 \bmod 187$

Теперь вычислим $13 в степени 4 \bmod 187: 13 в квадрате =16913 в степени 4 = левая круглая скобка 13 в квадрате правая круглая скобка в квадрате =169 в квадрате$ $\bmod 187169 в квадрате =2856128561 \bmod 187=28561 минус 153 \times 187=$ $28561 минус 28451=110$ Таким образом: $13 в степени 4 \equiv 110 \bmod 18713 в степени левая круглая скобка 160 правая круглая скобка \equiv 110 \bmod 18713 в степени левая круглая скобка 160 правая круглая скобка минус$ $1 \equiv 110 минус 1 \equiv 109 \bmod 187$ Однако, мы должны проверить, что $13 в степени левая круглая скобка 160 правая круглая скобка$ - 1 действительно делится на 187. Поскольку $13 в степени левая круглая скобка 160 правая круглая скобка \equiv 1 \bmod 13$ (из теоремы Эйлера), то: $13 в степени левая круглая скобка 160 правая круглая скобка минус 1 \equiv 1 минус 1 \equiv 0 \bmod 13$ Так как $13 в степени левая круглая скобка 160 правая круглая скобка минус 1$ делится на 13, и мы уже показали, что $13 в степени левая круглая скобка 160 правая круглая скобка \equiv 110$ $\bmod 187,$ то $13 в степени левая круглая скобка 160 правая круглая скобка$ - 1 действительно делится на 187.

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