2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

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

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

 
 
 
 Re: Сравнения
Сообщение23.12.2015, 23:17 
Спасибо! Получается так
$ 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}  $

 i  Lia: $ 5^4 \equiv\ x  \pmod {221}  $
Код:
$ 5^4 \equiv\ x  \pmod {221}  $

 
 
 
 Re: Сравнения
Сообщение23.12.2015, 23:55 
Аватара пользователя
А вообще решается за 8 умножений без всякой КТО.

 
 
 
 Re: Сравнения
Сообщение24.12.2015, 00:31 
demolishka
Можно поподробнее?

 
 
 
 Re: Сравнения
Сообщение24.12.2015, 00:40 
Аватара пользователя
$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 умножения.

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

 
 
 
 Re: Сравнения
Сообщение25.12.2015, 00:06 
Спасибо! Поняла ) Оказалось все намного проще))

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group