「モジュロ逆元」と「フェルマーの小定理」は、特に競技プログラミングや暗号などで頻繁に使われる数学的なツールです。順番に丁寧に説明します。

ある整数 a に対して、次の式を満たす整数 a⁻¹（mod M）が存在するとします：

a * a⁻¹ ≡ 1 (mod M)

この a⁻¹ を「a の モジュロ M における逆元」と言います。

M = 7 のとき、 a = 3 の逆元を探す → 3 * x ≡ 1 (mod 7)

試してみると：

• 3 × 5 = 15 ≡ 1 (mod 7)

なので 3⁻¹ ≡ 5 (mod 7)

たとえば nCr を求めるとき：

nCr = n! / (r! * (n - r)!)

でも「mod M」での計算では「/」が使えません！

代わりに逆元を使って次のように書きます：

nCr ≡ n! × (r!)⁻¹ × ((n - r)!)⁻¹ mod M

M が 素数で、a が M の倍数でない整数のとき：

a^(M-1) ≡ 1 (mod M)

これを使うと逆元を次のように計算できます：

a⁻¹ ≡ a^(M-2) (mod M)

「素数 M における逆元」は、a^(M-2) mod M で求められる！

function modInverse(a, mod) {
    return modPow(a, mod - 2, mod); // フェルマーの小定理
}

function modPow(a, b, mod) {
    let res = 1n;
    a = BigInt(a);
    b = BigInt(b);
    mod = BigInt(mod);
    while (b > 0) {
        if (b % 2n === 1n) res = (res * a) % mod;
        a = (a * a) % mod;
        b = b / 2n;
    }
    return res;
}

• M は必ず素数である必要があります！ フェルマーの小定理は「M が素数」という前提で成り立っています。
• M が素数でない場合は「拡張ユークリッドの互除法」で逆元を求める必要があります。