Найдите остаток при делении числа 3^20 на 8!! Найдите остаток при делении числа 3^20 на 8!!

Предыдущий
вопрос Следующий
вопрос

Для того чтобы найти остаток при делении числа (3^{20}) на (8!!), сначала вычислим значение (8!!).

(8!! = 8 \times 6 \times 4 \times 2 = 384).

Теперь вычислим остаток при делении (3^{20}) на 384. Мы можем использовать теорему об остатках:
[3^{20} \equiv x \pmod{384}]
где (0 \leq x < 384).

Теперь используем малую теорему Ферма: если (a) и (n) взаимно просты, то
[a^{\phi(n)} \equiv 1 \pmod{n},]
где (\phi(n)) - функция Эйлера, определяемая как количество целых чисел от 1 до (n), которые взаимно просты с (n). Для (n = 384) имеем (\phi(384) = \phi(2^7 \times 3) = 384 \times \frac{1}{2} \times \frac{2}{3} = 128).

Теперь вычисляем остаток (3^{20} \pmod{128}):
[3^{20} \equiv 3^{20 \pmod{128}} = 3^{20 \pmod{32}}]

Теперь, вычисляем (3^{20} \pmod{32}):
[3^{20} \equiv 3^0 \equiv 1 \pmod{32}]

Итак, мы нашли, что (3^{20} \equiv 1 \pmod{32}), и также мы знаем, что (3^{20} \equiv 1 \pmod{384}). Следовательно, остаток при делении (3^{20}) на 384 равен 1.

Таким образом, остаток при делении числа (3^{20}) на (8!! = 384) равен 1.