# Integer CRT

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

Solve a system of integer congruences (x ≡ remainder mod modulus) with the Chinese Remainder Theorem.

**Use when you need to: integer crt · chinese remainder theorem · solve system of congruences.**

## Supported

- integer crt
- chinese remainder theorem
- solve system of congruences
- combine modular congruences

## Not supported

- polynomial congruences
- non-integer moduli
- inconsistent system resolution

## Behavior

- congruences is an array of 1 to 100 objects, each with canonical integer-string remainder and a positive canonical integer-string modulus.
- remainder may be negative or exceed modulus; it is reduced into [0, modulus) before solving.
- Moduli need not be pairwise coprime; congruences are merged pairwise with a consistency check at each step.
- If any pair of congruences is inconsistent (no integer satisfies both), the request is rejected as unsolvable.
- The output is the unique remainder in [0, combined_modulus) together with combined_modulus, the least common multiple of every input modulus.
- A single congruence returns its own reduced remainder and modulus unchanged.
- Every modulus and the combined modulus may have at most 1000 digits excluding sign.

## Input

- `congruences` (array of object, required): min items 1; max items 100

## Output

- `remainder` (string, required)
- `modulus` (string, required)

## Limits

- max congruences: 100
- max digits: 1000

## Example

Request input:

```json
{
  "congruences": [
    {
      "remainder": "2",
      "modulus": "3"
    },
    {
      "remainder": "3",
      "modulus": "5"
    }
  ]
}
```

Response:

```json
{
  "result": {
    "remainder": "8",
    "modulus": "15"
  }
}
```

## How to call it

### MCP

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

```json
{
  "id": "integer-crt",
  "version": "1.0.0",
  "input": {
    "congruences": [
      {
        "remainder": "2",
        "modulus": "3"
      },
      {
        "remainder": "3",
        "modulus": "5"
      }
    ]
  }
}
```

### HTTP (no key)

```sh
curl -X POST https://computefirst.net/v1/tools/integer-crt/versions/1.0.0/execute \
  -H "Content-Type: application/json" \
  -d '{"congruences":[{"remainder":"2","modulus":"3"},{"remainder":"3","modulus":"5"}]}'
```

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

### CLI

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

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

## Related tools

- [Array integer adjacent diff](/tools/array-integer-adjacent-diff): Replace an array of canonical integer strings with consecutive first differences.
- [Array integer cumulative sum](/tools/array-integer-cumulative-sum): Replace an array of canonical integer strings with equal-length prefix sums.
- [Array integer GCD](/tools/array-integer-gcd): Compute the non-negative greatest common divisor of an array of canonical integer strings.
- [Array integer LCM](/tools/array-integer-lcm): Compute the non-negative least common multiple of an array of canonical integer strings.
- [Array integer median](/tools/array-integer-median): Select lower and upper middle canonical integers; emit median only for odd length.
- [Array integer min max](/tools/array-integer-min-max): Return the numeric minimum and maximum of canonical integer strings.