Номер 30.33, страница 249 - гдз по алгебре 8 класс учебник Мерзляк, Поляков

Глава 5. Основы теории делимости. Параграф 30. Простые и составные числа - номер 30.33, страница 249.

Условие.

30.33. Используя малую теорему Ферма, найдите остаток при делении числа $a$ на число $b$, если:

1) $a = 5^{52}$, $b = 53$;

2) $a = 2^{47}$, $b = 41$.

Решение.

1) Требуется найти остаток от деления $a = 5^{52}$ на $b = 53$.

Воспользуемся малой теоремой Ферма, которая утверждает, что если $p$ — простое число, то для любого целого числа $a$, не делящегося на $p$, справедливо сравнение: $a^{p-1} \equiv 1 \pmod{p}$.

В данном случае $p = 53$, что является простым числом. Основание степени $a = 5$ не делится на $53$. Таким образом, условия теоремы соблюдены.

Применяем теорему для наших значений:

$5^{53-1} \equiv 1 \pmod{53}$

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

Это сравнение показывает, что при делении $5^{52}$ на $53$ остаток равен 1.

Ответ: 1

2) Требуется найти остаток от деления $a = 2^{47}$ на $b = 41$.

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

Подставляем наши значения:

$2^{41-1} \equiv 1 \pmod{41}$

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

Нам нужно найти остаток для $2^{47}$. Представим показатель степени 47 через 40:

$2^{47} = 2^{40+7} = 2^{40} \cdot 2^7$

Теперь воспользуемся свойством сравнений и полученным результатом из теоремы Ферма:

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

$2^{47} \equiv 2^7 \pmod{41}$

Осталось вычислить $2^7$ и найти остаток от его деления на 41.

$2^7 = 128$

Разделим 128 на 41 с остатком:

$128 = 3 \cdot 41 + 5$

Остаток равен 5. Следовательно, $128 \equiv 5 \pmod{41}$, а значит, и $2^{47} \equiv 5 \pmod{41}$.

Ответ: 5