SG
← Back

Extended Euclidean Algorithm

Find gcd(a,b) and coefficients x,y with ax+by=gcd(a,b).

mathgcdnumber-theoryUpdated 2025-09-01

Recurrence

  • ext(a,b) → ext(b,a%b)

Uses

  • Mod inverse when gcd=1