Congruence Solver

Congruence Solver is a TypeScript library designed to solve linear and quadratic congruences, as well as systems of such equations. Unlike most other solvers, it gives the solutions with the least possible modulus, which in effect minimizes the number of distinct residues.

The library also provides access to underlying modular arithmetic utilities, including algorithms for calculating modular inverses and modular square roots.

Examples

Try the examples below on CodePen

Quadratic congruence

x² + 18x ≡ 0 (mod 27)

import {solveQuadraticCongruence} from 'congruence-solver';

const {res, mod} = solveQuadraticCongruence(1, 18, 0, 27);
console.log(`x ≡ ${res} (mod ${mod})`);  // x ≡ 0 (mod 9)

For comparison, WolframAlpha returns x ≡ 0 (mod 27), x ≡ 9 (mod 27), x ≡ 18 (mod 27)

Pre-factored modulus

If the prime factors of the modulus are known, they can be passed as an Array of numbers in increasing order.

3x² + 4x + 5 ≡ 0 (mod 2·2·3·5)

import {solveQuadraticCongruence} from 'congruence-solver';

const inputModFactors = [2, 2, 3, 5];
const {res, mod} = solveQuadraticCongruence(3, 4, 5, inputModFactors);
console.log(`x ≡ ${res} (mod ${mod})`);  // x ≡ 7,25 (mod 30)

Congruence system

3x + 1 ≡ 0 (mod 10)
4x + 3 ≡ 0 (mod 15)
x² + x + 2 ≡ 0 (mod 4)

import {intersectResidues, solveLinearCongruence, solveQuadraticCongruence} from 'congruence-solver';

const {res, mod} = intersectResidues(
    solveLinearCongruence(3, 1, 10),
    solveLinearCongruence(4, 3, 15),
    solveQuadraticCongruence(1, 1, 2, 4));

console.log(`x ≡ ${res} (mod ${mod})`);  // x ≡ 33 (mod 60)

Primitives

import {factor, gcd, inverseMod, powMod, sqrtModPrime} from 'congruence-solver';

const LOOSE = false;

console.log(`Prime factors of 315: ${factor(315)}`);              // 3,3,5,7
console.log(`gcd(121, 143) = ${gcd(121, 143)}`);                  // 11
console.log(`2^-1 ≡ ${inverseMod(2, 5)} (mod 5)`);                // 3
console.log(`10^-1 (mod 15) is ${inverseMod(10, 15)}`);           // NaN
console.log(`4·${inverseMod(4, 6, LOOSE)} ≡ gcd(4, 6) (mod 6)`);  // 2
console.log(`3⁸ ≡ ${powMod(3, 8, 7)} (mod 7)`);                   // 1
console.log(`√3 (mod 11) = ±${sqrtModPrime(3, 11)}`);             // ±5