Сравнения

[MariaKh]

Добрый вечер! Подскажите пожалуйста как это решать? Ничего похожего не нашла, везде пользуются теоремой Эйлера ,но тут она не подходит. Как подступиться?

$5^ {63} \equiv\ x \pmod {221}$

[Mihr]

Попробуйте, например, в качестве вспомогательной задачи найти, с чем сравнимо по данному модулю $5^{4} (или другая небольшая степень пятёрки).
И вспомните, что целым рядом свойств сравнения похожи на равенства. Что можно делать со сравнениями?

[AV_77]

Сначала перейти к сравнениям по простым делителям $221$, а потом китайская теорема об остатках.

[MariaKh]

Спасибо! Получается так
$ 5^4 \equiv\ x \pmod {221} $
$\begin{cases} 5^4 \equiv\ x \pmod {13} \\ 5^4 \equiv\ x \pmod {17} \end{cases}$

$\begin{cases} x \equiv\ 1 \pmod {13 }\\ x \equiv\ 13 \pmod {17} \end{cases}$
Из первого выражаем $x$ и подставляем во второе
$ x=13t+1 $
$ 13t \equiv\ 12 \pmod {17} $
$ t \equiv\ 14 \pmod {17} $
$ t= 17 t_1 +14 $
$ x = 221t_1 +183$
$x \equiv\ 183 \pmod {221} $

Lia: $ 5^4 \equiv\ x \pmod {221} $

$ 5^4 \equiv\ x  \pmod {221}  $

[demolishka]

А вообще решается за 8 умножений без всякой КТО.

[MariaKh]

demolishka
Можно поподробнее?

[whitefox]

$5^{63}\equiv5^{21}\cdot5^{21}\cdot5^{21}\pmod{221}$
$5^{21}\equiv5^7\cdot5^7\cdot5^7\pmod{221}$
И $5^7\bmod 221$ вычисляется за 4 умножения.

[Mihr]

MariaKh,
можно, конечно, и так. Но, по-моему, быстрее было бы из 625 два раза вычесть 221.
Потом из $5^4$ и $5^3$ строим $5^7$.
И дальше - как сказал whitefox.

[MariaKh]

Спасибо! Поняла ) Оказалось все намного проще))