Найдите остаток от деления а) 5^20 на 24; б) 3^66 на 28. Надо использовать сравнение по модулю

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

a) 5^20 ≡ 1 (mod 24)

Так как 5 и 24 взаимно простые, то мы можем возвести 5 в степень, равную φ(24) = φ(2^3 3) = 2^2 2 = 8, где φ(n) - функция Эйлера, которая указывает на количество чисел взаимно простых с n и меньше n.

Таким образом, 5^20 ≡ 5^4 ≡ 25^2 ≡ 1^2 ≡ 1 (mod 24)

Ответ: остаток от деления 5^20 на 24 равен 1.

б) 3^66 ≡ 1 (mod 28)

Аналогично предыдущему пункту, мы можем возвести 3 в степень, равную φ(28) = φ(2^2 7) = 2^1 6 = 12.

Таким образом, 3^66 ≡ 3^6 ≡ 729^2 ≡ 1^2 ≡ 1 (mod 28)

Ответ: остаток от деления 3^66 на 28 равен 1.