# Integer extended GCD

`integer-extended-gcd` · version 1.0.0 · Numbers & math · free, no key needed

Compute the extended Euclidean algorithm result: gcd(a, b) and Bezout coefficients x, y with a*x + b*y = gcd.

**Use when you need to: integer extended gcd · extended euclidean algorithm · bezout coefficients.**

## Supported

- integer extended gcd
- extended euclidean algorithm
- bezout coefficients
- bezout identity

## Not supported

- plain gcd without coefficients
- lcm
- modular inverse of a non-coprime pair

## Behavior

- Inputs are canonical integer strings: 0 or an optional ASCII minus followed by a non-zero leading digit.
- The input -0 is accepted and canonicalized to 0 before evaluation.
- a = 0 and b = 0 together are rejected: the gcd is undefined.
- gcd is the non-negative greatest common divisor of a and b.
- x and y are Bezout coefficients satisfying a*x + b*y = gcd exactly, using the original signed a and b.
- x and y are not unique; this contract returns the pair produced by the standard iterative extended Euclidean algorithm.
- Each input and each output field may have at most 1000 digits excluding sign.

## Input

- `a` (string, required): min length 1; max length 1001
- `b` (string, required): min length 1; max length 1001

## Output

- `gcd` (string, required)
- `x` (string, required)
- `y` (string, required)

## Limits

- max digits: 1000

## Example

Request input:

```json
{
  "a": "35",
  "b": "15"
}
```

Response:

```json
{
  "result": {
    "gcd": "5",
    "x": "1",
    "y": "-2"
  }
}
```

## How to call it

### MCP

Connect `https://computefirst.net/mcp` ([setup](/docs#connect)), then call `execute` with:

```json
{
  "id": "integer-extended-gcd",
  "version": "1.0.0",
  "input": {
    "a": "35",
    "b": "15"
  }
}
```

### HTTP (no key)

```sh
curl -X POST https://computefirst.net/v1/tools/integer-extended-gcd/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"a":"35","b":"15"}'
```

The machine-readable contract is at [/v1/tools/integer-extended-gcd/versions/1.0.0](/v1/tools/integer-extended-gcd/versions/1.0.0).

### CLI

```sh
node cli.mjs run integer-extended-gcd 1.0.0 --input input.json --base-url https://computefirst.net
```

Get the client at [/clients/cli/](/clients/cli/).

## Related tools

- [Array integer GCD](/tools/array-integer-gcd): Compute the non-negative greatest common divisor of an array of canonical integer strings.
- [Integer GCD](/tools/integer-gcd): Compute the non-negative greatest common divisor of two canonical integer strings.
- [Array integer adjacent diff](/tools/array-integer-adjacent-diff): Replace an array of canonical integer strings with consecutive first differences.
- [Array integer clamp](/tools/array-integer-clamp): Clamp an array of canonical integer strings to optional inclusive min and max bounds.
- [Array integer cumulative sum](/tools/array-integer-cumulative-sum): Replace an array of canonical integer strings with equal-length prefix sums.
- [Array integer LCM](/tools/array-integer-lcm): Compute the non-negative least common multiple of an array of canonical integer strings.