3.14Обратное по модулю.

Малая теорема Ферма утверждает, что a^n-1 mod n=1 для простого n и не кратного ему a.

Функция Эйлера φ(n) – количество целых положительных чисел, меньших n и взаимно простых с n. Эйлер показал, что для простого n φ(n)=n-1, для n=p*q, где p и q – простые числа, φ(n)=(p-1)*(q-1)=m.

a^n-1 mod n=1 по теореме Ферма. Для простого n a^φ(n) mod n=1. Таким образом, обратное a по модулю n рассчитывается как a^φ(n)-1 mod n.