Extended Euclidean Algorithm

Updated 13 Sep 2026

• •

  What it is

  • •

    n extension of Euclid's algorithm that, alongside $\gcd(a,b)$, also returns integers $u, v$ satisfying Bézout's identity $au + bv = \gcd(a,b)$.

• •

  When to apply

  • •

    Whenever you need a modular inverse under a modulus that isn't necessarily prime, or need to combine two moduli/coefficients into a single linear relationship (e.g. building blocks for CRT or RSA key generation).

• •

  Symbols and assumptions

  • •

    $a,b$ are integers; $d=\gcd(a,b)$ is their greatest common divisor. Bézout coefficients $u,v$ satisfy $au+bv=d$. An inverse of $a$ modulo $b$ exists exactly when $d=1$.

• •

  Math — step by step

  • •
    1. Divide with remainder: $a=qb+r$. A number divides both $a,b$ exactly when it divides both $b,r$, because $r=a-qb$. Therefore replacing $(a,b)$ by $(b,r)$ preserves the gcd.
  • •
    2. Repeat until the remainder is zero. The final nonzero remainder is the gcd. Each division also writes one remainder as an integer combination of the previous two.
  • •
    3. Substitute those remainder equations backward until the gcd is written using the original $a,b$. Reduce $au+bv=1$ modulo $b$: the $bv$ term vanishes, leaving $au\equiv1\pmod b$. Thus $u\bmod b$ is the inverse.
• •

  Worked example

  • •

    Find $7^{-1}\bmod26$. Divisions: $26=3\cdot7+5$; $7=1\cdot5+2$; $5=2\cdot2+1$; $2=2\cdot1+0$. The gcd is 1.

  • •

    Back-substitute: $1=5-2\cdot2=5-2(7-5)=3\cdot5-2\cdot7=3(26-3\cdot7)-2\cdot7=3\cdot26-11\cdot7$.

  • •

    The coefficient of 7 is $-11$, so its inverse is $-11\bmod26=15$. Check: $7\cdot15=105=4\cdot26+1$. Python: pow(7, -1, 26) == 15.

• •

  Python

  • •

    def extended_gcd(a, b):
        if b == 0:
            return a, 1, 0
        g, x1, y1 = extended_gcd(b, a % b)
        return g, y1, x1 - (a // b) * y1
    

• •

  SageMath

  • •

    g, u, v = xgcd(26513, 32321)   # (1, 10245, -8404)
    

• •

  Related

  • •

    Chinese Remainder Theorem

  • •

    Fermat's Little Theorem

• •

  Cards

  • •

    What does Bézout's identity state?

    • •

      For integers a, b there exist integers u, v such that $au + bv = \gcd(a,b)$.

  • •

    What extra outputs does the extended Euclidean algorithm give beyond the plain gcd?

    • •

      The Bézout coefficients u and v.

◌ Explore connections in Graph view