Question

Найти остаток от деления 7^60 на 143 используя малую теорему Ферма

Answer 1

Ответ: 1

Объяснение:

Добрый вечер!

Заметим, что $143=11*13$

Малая теорема Ферма гласит, что для любого простого числа $p$ и натурального числа $\alpha$ , где  $a<p$ , справедливо равенство:

$a^{p-1} mod p = 1$

Найдем:  $7^{60} mod 13$

$7^{60}mod13 = (7^{12})^5 mod 13$

Заметим, что число 13 простое, причем 7<13, тогда можно применить малую теорему Ферма:

$7^{12} mod 13 = 1$

Другими словами:

$7^{12} = 13n+1$, где $n$- натуральное число

$(7^{12})^5 = (13n+1)^5$

Заметим, что в биноме Ньютона $(13n+1)^5$ все члены, кроме члена $1^5=1$, помножены на некоторую степень числа 13, а значит данное выражение дает при делении на 13 остаток 1.

$7^{60} mod13=1$

Найдем: $7^{60} mod 11$

Число 11 простое, и 7<11, тогда рассуждая аналогично имеем:

$7^{10} mod 11 = 1\\(7^{10})^6 mod 11 = 1\\7^{60} mod 11 = 1$

Таким образом :

$7^{60} mod 11 =7^{60} mod 13 = 1$ ,поскольку 11 и 13- взаимнопростые

$7^{60} mod 143 = 1$