Extended Euclidean Algorithm

Small Python utilities to compute GCD, Bezout coefficients, and modular inverses using the Extended Euclidean Algorithm.

Files

• large_modular_inverse.py — compute modular inverse via extended_euclid(a, b) and mod_inv(a, n).
• extended_euclid_table.py — show step-by-step algorithm table with extended_euclid_table(a, b) and print_table(rows).

Math

Finds integers x, y such that a*x + b*y = gcd(a, b). If gcd(a, n) = 1, then x is the modular inverse of a mod n.

Usage

Run examples:

python large_modular_inverse.py
python extended_euclid_table.py