JavaScriptで拡張ユークリッドの互除法

JavaScriptで拡張ユークリッドの互除法をスッキリ書けないのかと試行錯誤した結果。

const exGcd = (n, m) => m === 0 ? [1, 0, n] : _exGcd(div(n, m), exGcd(m, mod(n, m)));

const _exGcd = (q, [y, x, d] = []) => [x, y - x * q, d];

const div = (n, m) => (n - mod(n, m)) / m;

const mod = (n, m) => (Math.abs(m) + (n % m)) % m;

アルゴリズムの詳細は拡張ユークリッドの互除法 〜 一次不定方程式 ax + by = c の解き方 〜に詳しいです。

雑なテスト

const gcd = (n, m) => m === 0 ? n : gcd(m, mod(n, m));

const randInt = (min, max) => Math.floor(Math.random() * max - min + 1) + min;

const n = randInt(-100, 100);
const m = randInt(-100, 100);
const [x, y, d] = exGcd(n, m);

console.log([n, x, m, y, d]);
console.log(n * x + m * y === d);
console.log(gcd(n, m) === d);