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

Ответ: 1

Объяснение:

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

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

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

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

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

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

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

$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.