Extended Euclidean Algorithm
(math/extgcd.hpp)

• View this file on GitHub
• Last update: 2026-01-09 14:45:55+09:00
• Include: #include "math/extgcd.hpp"

Computes $g = \gcd(a,b)$ and find integers $x$ and $y$ such that $ax+by=g$.

• $g$ may be negative.
• $\lvert x \rvert \le \left\lvert \frac{b}{g} \right\rvert$
• $\lvert y \rvert \le \left\lvert \frac{a}{g} \right\rvert$

Bézout’s identity—Let $a$ and $b$ be integers with greatest common divisor $g$. Then there exist integers $x$ and $y$ such that $ax + by = g$. Moreover, the integers of the form $az + bt$ are exactly the multiples of $g$.

Complexity

• $ \mathcal{O(\log(\min(a, b)))} $

References

• euclid.h - KACTL
• Extended Euclidean Algorithm - CP Algorithms
• Extended Euclidean algorithm - Wikipedia
• Bézout’s identity - Wikipedia
• Proof of Bounds for the Extended Euclidean Algorithm - Jeffrey Hurchalla

Verified with

• test/math/extgcd.test.cpp

Code

#ifndef EXTGCD_HPP
#define EXTGCD_HPP

template <typename T> T extgcd(T a, T b, T &x, T &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    T d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

#endif // EXTGCD_HPP

#line 1 "math/extgcd.hpp"



template <typename T> T extgcd(T a, T b, T &x, T &y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    T d = extgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

Back to top page