# xgcd() Function & Examples

Use the xgcd() arithmetic function in Calcul.io. Review its syntax, edit working examples, understand the result, and explore related math functions.

## xgcd

#### xgcd(a, b)

Try it yourself:

```calculio
xgcd(8, 12)
gcd(8, 12)
xgcd(36163, 21199)
```

[gcd](https://calcul.io/function/gcd/index.md)

[lcm](https://calcul.io/function/lcm/index.md)

---

## Find Bézout coefficients with xgcd

**xgcd(a, b)** uses the extended Euclidean algorithm to find the greatest common divisor of two integers together with coefficients that express that divisor as a linear combination of the inputs. In other words, it finds values g, x, and y such that `a*x + b*y = g`, where g is the gcd of a and b.

## Why the extended result is useful

The ordinary [gcd](https://calcul.io/function/gcd/index.md) function answers how large the common divisor is. Xgcd additionally supplies the coefficients needed to solve linear Diophantine equations and find modular inverses. For example, if the gcd of a and a modulus m is 1, the coefficient of a can be reduced modulo m to obtain an inverse; [invmod](https://calcul.io/function/invmod/index.md) provides that direct modular-inverse task.

## Example

For inputs 30 and 18, the gcd is 6, and xgcd supplies coefficients satisfying `30*x + 18*y = 6`. Those coefficients are not necessarily unique, but any returned pair proves the identity. Use [mod](https://calcul.io/function/mod/index.md) to bring an inverse or coefficient into a preferred non-negative residue range, and [lcm](https://calcul.io/function/lcm/index.md) when the least common multiple is needed instead.

## Input caveats

Use integer inputs for the standard number-theory interpretation. Signs can affect the reported coefficients even though gcd is conventionally non-negative. If both inputs are zero, the usual Bézout identity is degenerate, so handle that case explicitly. Xgcd is not a replacement for [divide](https://calcul.io/function/divide/index.md) when ordinary numeric division is the actual goal.

[All functions](https://calcul.io/functions/index.md)