Question

помогите пожалуйста!!!​

Answer 1

Ответ:

(см. объяснение)

Пошаговое объяснение:

Знаем, что верно:

$3^{205}\mod125=(3^5\times3^{200})\,\mathrm{mod}\,125=(3^5\mod125\;\times\;3^{200}\mod125)\mod125$

Заметим теперь, что $3^{100}=3^{\varphi(125)}$, где $\varphi(x)$ - функция Эйлера.

Действительно $\varphi(125)=\varphi(5^3)=5^3-5^{3-1}=100$.

Поскольку $3$ и $125$ взаимно просты, то по т. Эйлера $3^{100}=1\mod 125$.

Знаем, что если $a=b\mod m$, то $a^n=b^n\,\mathrm{mod}\, m$, то есть $3^{200}=1\mod 125$.

Тогда получили, что:

$3^{205}\mod125=(3^5\mod125\;\times1)\mod125=3^5\mod125=118$

Задание выполнено!