Extended Euclidean Solver
OperatorsMediumCompute Greatest Common Divisor and Bézout coefficients (x, y) satisfying Diophantine relations.
Alt+Shift+7
Configuration Panel
Complexity Indices
Time ComplexityO(log(min(A, B)))
Auxiliary SpaceO(log(min(A, B)))
Conceptual Overview
Extended Euclidean Algorithm finds integer coefficients (x, y) satisfying Bézout's identity: ax + by = gcd(a, b), which is useful for modular inverses.
Source: CP-Algorithms reference guide