Редукция по модулю

[Stasya7]

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

[StaticZero]

(TeX)

Наведите мышкой на примеры, чтобы узнать код.

$$ 5^{50} \pmod {101}$$

$$5^{50} \mod 101$$

$$5^{50} \bmod 101$$

[Simple Fairy]

Если я правильно понимаю, то $ 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.

[bot]

Simple Fairy в сообщении #1160179 писал(а):

И в вашем случае 50 является делителем 100

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