Extended GCD
Type the integers whose GCD you want to compute. Note that in the equations below, each step starting
from the base case preserves the invariant
\[af + bd = c\]
Because at each step we generate a linear combination of two equations that satisfy the invariant, the resulting
equation also preserves the invariant. The extended gcd algorithm finds \(f^{-1} \pmod{d}\) and
\(d^{-1} \pmod{f}\) when \(gcd(f,d) = 1\).