> ## Documentation Index
> Fetch the complete documentation index at: https://docs.starknet.io/llms.txt
> Use this file to discover all available pages before exploring further.

# core::math::egcd

Computes the extended GCD and Bezout coefficients for two numbers.
Uses the Extended Euclidean algorithm to find (g, s, t, sub\_direction) where `g = gcd(a, b)`.
The relationship between inputs and outputs is:

* If `sub_direction` is true:  `g = s * a - t * b`
* If `sub_direction` is false: `g = t * b - s * a`

Returns a tuple (g, s, t, sub\_direction) where g is the GCD and `(s, -t)` or `(-s, t)` are the
Bezout coefficients (according to `sub_direction`).

## Signature

```rust theme={null}
pub fn egcd,
    +Drop,
    +Add,
    +Mul,
    +DivRem,
    +core::num::traits::Zero,
    +core::num::traits::One,
    +TryInto>,
>(
    a: NonZero, b: NonZero,
) -> (T, T, T, bool)
```

## Examples

```rust theme={null}
use core::math::egcd;

let (g, s, t, dir) = egcd::(12, 8);
assert!(g == 4);
```