Question

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

Answer 1

Ответ: 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, тогда можно применить малую теорему Ферма:

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

Answer 2

Для нахождения остатка от деления $7^{60}$ на 143 с использованием малой теоремы Ферма, нам сначала нужно проверить, что 7 и 143 являются взаимно простыми числами (то есть их наибольший общий делитель равен 1). Это верно, так как 7 и 143 не имеют общих делителей, кроме 1.

Малая теорема Ферма гласит, что если $p$ - простое число, а $a$ - целое число, не кратное $p$, то:

$a^{p-1} \equiv 1 \pmod{p}$

В данном случае $p = 7$, и мы хотим найти остаток от деления $7^{60}$ на 7. По малой теореме Ферма:

$7^{7-1} \equiv 1 \pmod{7}$

$7^6 \equiv 1 \pmod{7}$

Теперь мы знаем, что $7^6$ дает остаток 1 при делении на 7. Теперь мы можем использовать это для нахождения остатка от деления $7^{60}$ на 143.

$7^{60} = (7^6)^{10}$

Теперь мы можем возвести 1 в степень 10:

$1^{10} = 1$

Таким образом, остаток от деления $7^{60}$ на 143 равен 1.