Question

Найти остаток от деления числа а на m a=15^254 (mod)19

Answer 1

$15^{254}=\equiv (-4)^{2*127}(mod\:19)=16^{127}\equiv(-3)^{127}(mod\:19)=-27*(-3)^{4*31}=(-27)*81^{31}\equiv (-8)*5^{31}(mod\:19)=(-40)*25^{15}\equiv(-2)*6^{15}(mod\:19)=(-12)*36^7\equiv 7*(-2)^7(mod\:19)=(-7)*16*8\equiv (-7)*(-3)*8(mod\:19)=21*8\equiv 16(mod\:19)$

Answer 2

Чтобы найти остаток от деления числа a на m, нужно вычислить значение a (mod m).

В данном случае, необходимо найти остаток от деления 15^254 на 19.

Для того, чтобы решить эту задачу, можно воспользоваться малой теоремой Ферма, которая гласит, что если p – простое число, а a – целое число, не делящееся на p, то a^(p-1) ≡ 1 (mod p).

В данной задаче m=19, что является простым числом. Поэтому, применяя малую теорему Ферма, можно получить:

15^(18) ≡ 1 (mod 19)

Таким образом, чтобы решить задачу, нужно разделить показатель степени 254 на 18 и найти остаток от этого деления.

254 ÷ 18 = 14 с остатком 2

Значит,

15^(254) ≡ 15^(18*14+2) ≡ (15^18)^14 * 15^2 ≡ 1^14 * 225 ≡ 5 (mod 19)

Таким образом, остаток от деления числа 15^254 на 19 равен 5.

Ответ: 5.