Упр.30.33 ГДЗ Мерзляк Поляков 8 класс (Алгебра)

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

1. Так как $$53$$ — простое число, по малой теореме Ферма имеем:

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

   Тогда

   $$5^{53}-5\equiv 0 \pmod{53},$$

   то есть

   $$5\left(5^{52}-1\right)\equiv 0 \pmod{53}.$$

   Так как $$5\not\equiv 0 \pmod{53},$$ получаем:

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

2. Так как $$41$$ — простое число, по малой теореме Ферма:

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

   Тогда

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

   Вычислим:

   $$2^7=128,$$

   $$128\equiv 5 \pmod{41}.$$

   Значит,

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

Ответ

1) $$1$$; 2) $$5$$.