Найти остаток от деления с помощью теоремы Эйлера (5^211) / 22

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

Для нахождения остатка от деления числа (5^{211}) на 22 с помощью теоремы Эйлера, сначала найдем значение функции Эйлера от 22.

Так как 22 = 2 11 и 2 и 11 - простые числа, то функция Эйлера от 22 равна (\phi(22) = \phi(2) \phi(11) = (2-1)*(11-1) = 10).

Теперь по теореме Эйлера: для любого целого числа (a), взаимно простого с 22, выполняетс
[a^{\phi(22)} \equiv 1 \pmod{22}]

Так как 5 и 22 взаимно просты (наибольший общий делитель равен 1), т
[5^{10} \equiv 1 \pmod{22}]

Следовательно
[5^{211} = 5^{10 21 + 1} = (5^{10})^{21} 5 \equiv 1^{21} * 5 \equiv 5 \pmod{22}]

Таким образом, остаток от деления числа (5^{211}) на 22 равен 5.