Как получить модульную инверсию с помощью расширенного евклидова алгоритма?

Если gcd(a,b) != 1, a не имеет обратного mod b.

В противном случае ax + by = 1 означает, что ax = 1 (mod b), поэтому x является инверсией a по модулю b.

Сделайте это, чтобы вычислить обратную зависимость x от модуля m:

function inverse(x, m)
    a, b, u := 0, m, 1
    while x > 0
        q, r := divide(b, x)
        x, a, b, u := b % x, u, x, a - q * u
    if b === 1 return a % m
    error("must be coprime")

Здесь := — это оператор одновременного присваивания, поэтому сначала выполняются все вычисления в правой части, а затем выполняются все присваивания. Функция divide возвращает как частное, так и остаток от b / x.