Function canonicalInteger

src/compute-engine/numerics/numeric-bigint.ts:19–34

(
  n: bigint,
  exponent: number
)

 * where `g = gcd(a, b)` (its sign follows `a`/`b`; callers that need a
 * non-negative `g` normalize the triple).
 */
export function extGcd(a: bigint, b: bigint): [bigint, bigint, bigint] {
  let [oldR, r] = [a, b];
  let [oldS, s] = [1n, 0n];
  let [oldT, t] = [0n, 1n];
  while (r !== 0n) {
    const q = oldR / r;
    [oldR, r] = [r, oldR - q * r];
    [oldS, s] = [s, oldS - q * s];
    [oldT, t] = [t, oldT - q * t];
  }
  return [oldR, oldS, oldT];
}

/**
 * The modular multiplicative inverse of `a` modulo `m` (`m > 0`): the integer
 * `x` in `[0, m)` with `a·x ≡ 1 (mod m)`, or `null` when `a` and `m` are not
 * coprime (i.e. `gcd(a mod m, m) ≠ 1`).
 */