2014 dxdy logo

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

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




 
 Редукция по модулю
Сообщение15.10.2016, 23:55 
Пусть требуется вычислить, например, $5^{50} (101)$. Я вычисляю где-то за 7-8 итераций. Может, можно быстрее? Может, есть какой-нибудь быстрый метод вычисления вот таких степеней?

 
 
 
 Re: Редукция по модулю
Сообщение16.10.2016, 00:04 
Аватара пользователя

(TeX)

Наведите мышкой на примеры, чтобы узнать код.$$
5^{50} \pmod {101}$$
$$5^{50} \mod 101$$
$$5^{50} \bmod 101$$

 
 
 
 Re: Редукция по модулю
Сообщение16.10.2016, 02:45 
Если я правильно понимаю, то $ a^{p-1}\equiv 1 \mod p$, и наименьшее $a^e \equiv 1 \mod p$ такое, что
$p-1=ek+r; 0\leq r < e$, т.е. грубо говоря, $e$ является делителем $p-1$. И в вашем случае 50 является делителем 100, а значит и сравнимо с единицей по модулю 101.

 
 
 
 Re: Редукция по модулю
Сообщение16.10.2016, 06:15 
Аватара пользователя
Simple Fairy в сообщении #1160179 писал(а):
И в вашем случае 50 является делителем 100

Ну, делителей у 100 много, вот хотя бы и 1, однако $5^{1}-1\not\equiv 0\pmod{101}$.
Из теоремы Ферма мы доподлинно только знаем, что $5^{100}-1\equiv 0\pmod{101}$
Stasya7, а какими средствами Вы владеете, про квадратичные вычеты слышали?

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


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