aⁿ (mod m) = a*a* …* a (mod m)

Теорема (Эйлера): Если m>1 и (a,m)=1, то a^φ(m) ≡ 1 (mod m).

Следствие (теорема Ферма): Если простое p не делит a, то a^p-1 ≡ 1 (mod p).
Определение: a^-1 обратно к a по mod m, если a*a^-1 ≡ 1 (mod m).

Определение: Порядок числа по mod m есть наименьшая степень t, что a^t ≡ 1 (mod m).

Комментарии запрещены.