Упр.49.21 ГДЗ Мерзляк 10 класс Углубленный уровень (Алгебра)

1. Используя малую теорему Ферма, найдите остаток от деления числа $$a$$ на число $$b$$, если:
   1) $$a=5^{52}$$, $$b=53$$;
   2) $$a=2^{47}$$, $$b=41$$.

Используем малую теорему Ферма: если число $$p$$ — простое и $$a$$ не делится на $$p$$, то $$a^{p-1}\equiv 1 \pmod p$$.

1. $$53$$ — простое число, значит

   $$5^{52}\equiv 1 \pmod{53}.$$

   Следовательно, остаток от деления числа $$5^{52}$$ на $$53$$ равен $$1$$.

2. $$41$$ — простое число, значит

   $$2^{40}\equiv 1 \pmod{41}.$$

   Тогда

   $$2^{47}=2^{40}\cdot 2^7\equiv 2^7 \pmod{41}.$$

   Вычислим:

   $$2^7=128,\qquad 128=41\cdot 3+5.$$

   Значит,

   $$2^{47}\equiv 5 \pmod{41}.$$

   Следовательно, остаток от деления числа $$2^{47}$$ на $$41$$ равен $$5$$.

Ответ: 1) $$1$$; 2) $$5$$.