Question

Знайти залишок при діленні 9^176 на 59

Answer 1

Ответ: Остаток равен 22

Объяснение:

Число 59 простое ,  согласно   теореме Эйлера  

Если a  такое число, что a, m  взаимно простые , то ${a}^{\varphi (m)}\equiv 1~(\mod \ m)$

Таким образом :

$\varphi (59) =59 \bigg(1-\dfrac{1}{59}\bigg ) = 58$

$9^{\varphi(59) } \equiv 1 (\mod 59) \\\\ 9^{58}\equiv 1 (\mod 59)$

Соответственно :

$9^{176} = 9^{3\cdot 58}\cdot 9^2 \equiv 9^2 \equiv 81 \equiv 22$

И мы получим остаток :

$9^{176} \equiv 22 (\mod 59)$

#SPJ1