Ответ:

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

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

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

[tex]3^{205}\mod125=(3^5\times3^{200})\,\mathrm{mod}\,125=(3^5\mod125\;\times\;3^{200}\mod125)\mod125[/tex]

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

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

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

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

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

[tex]3^{205}\mod125=(3^5\mod125\;\times1)\mod125=3^5\mod125=118[/tex]

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