C2: Modular Inverse

Editorial

The extended Euclidean algorithm is a classical algorithm that finds integer pairs $(x, y)$ that satisfy $ax + Ly = \mathrm{gcd}(a, L)$.

In this problem, since $a$ and $L$ are coprime ($\mathrm{gcd}(a, L) = 1$), you can find an integer pair $(x, y)$ that satisfies $ax + Ly = 1$.

Rewriting $ax + Ly = 1$ as $ax = 1 - Ly$, and taking both sides modulo $L$, we obtain $ax = 1 \bmod L$.

Thus, we conclude that $x = a^{-1} \bmod L$.

By using the extended Euclidean algorithm, we can efficiently compute $x$.

Since $L$ is not necessarily a prime number in this problem, we cannot use Fermat's little theorem.

Sample Code

Below is a sample program:

# Extended Euclidean Algorithm
 
 
def extended_euclidean(a: int, b: int) -> tuple[int, int, int]:
    # when b == 0:
    if b == 0:
        return a, 1, 0
 
    # recursive step
    gcd, x1, y1 = extended_euclidean(b, a % b)
 
    # update x and y
    x = y1
    y = x1 - (a // b) * y1
 
    return gcd, x, y
 
 
def solve(a: int, L: int) -> int:
    _, x, _ = extended_euclidean(a, L)
 
    return x % L