Модульная арифметика

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

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

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

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


Оставить комментарий





Статистика

Рейтинг@Mail.ru