逆元と剰余演算

ここでは、フェルマーの小定理を使って、剰余演算で逆元を求める計算について見ていきます。

逆元と剰余演算

フェルマーの小定理で見た内容を使って、商の剰余演算について見ていきます。この定理は次のような内容でした。

この式を変形すると、\[ a\cdot a^{p-2} \equiv 1 \pmod p \]となります。これは、 $\bmod p$ の世界では、 $a$ と $a^{p-2}$ を掛けると $1$ になる、ということです。

一般に、 $a$ にある値を掛けて $1$ になるとき、その値のことを $a$ の逆元(inverse element) といいます。逆数と似ていますが、逆数は数の掛け算での話をしているのに対し、逆元は $\bmod$ の世界も含めた、もっと広い世界での話をしています。逆元は、逆数を一般化したもの、ということもできます。

逆元と剰余演算の具体例

さて、ここからは具体的にコードを書いてみます。まず、次の問題を見てみましょう：AtCoder ABC F - Surrounded Nodes 。これを解くわけではありませんが、注記のところを見てみましょう。答えを有理数 $\dfrac{y}{x}$ の形にしてから、 $xz\equiv y \pmod {10^9+7}$ を満たす $z$ を答えなさい、となっていますね。これは要するに、 $x$ の逆元に $y$ を掛けたものを答えなさい、ということです。

続いて、入力例1・出力例1を見てみましょう。答えは $\dfrac{1}{8}$ だから $125000001$ を出力する、と書いていますね。これは、 $8$ の逆元が $125000001$ である、という意味です。この $125000001$ をどのようにして求めるのか、この計算だけを考えてみましょう。

素数と合成数などでも触れましたが、 $10^9+7$ は素数です。そのため、フェルマーの小定理から、 $x$ の逆元は $x^{10^9+7-2}$ であることがわかります。なので、例えば、 $8$ の逆元なら $8^{10^9+7-2} \pmod {10^9+7}$ を計算すればいいことがわかります。

ただ、少し難しい点が残っています。そのまま $10^9+7-2$ 乗を計算すると時間オーバーになってしまうんですね。そのため、そのまま掛けて答えを出すわけにはいきません。しかし、この問題をクリアする方法はすでに見ています。繰り返し二乗法と再帰関数で見たように、繰り返し二乗法を使えばいいですね。

以上から、正の整数を受け取って、 $\bmod {10^9+7}$ の世界での逆元を返すコードは次のように書くことができます。

#include <iostream>
using namespace std;

long long MOD = 1e9 + 7;

long long modPow(long long x, long long a) {
  if (a == 1) return x;
  if (a % 2) return (x * modPow(x, a - 1)) % MOD;
  long long t = modPow(x, a / 2);
  return (t * t) % MOD;
}

long long modInv(long long x) {
  return modPow(x, MOD - 2);
}

int main() {
  long long x; cin >> x;
  cout << modInv(x);
  return 0;
}

x を受け取って、 $\bmod 10^9+7$ での逆元を返す modInv を使って答えを出力しています。 modInv は、フェルマーの小定理から、x の MOD - 2 乗を計算しています。

この MOD - 2 乗の計算は、modPow で行っています。a 乗を計算する際、1 なら x を返し、それ以外の奇数なら、1 と a - 1 に分けて計算しています。偶数乗であれば、a を半分にしてから同じものを2回掛ける、という処理をしています。こうして指数をどんどん減らしていくことで、高速に a 乗を計算できます。繰り返し二乗法を使った計算です。

実際に 8 を入力すれば、125000001 が返ってきます。こうして、 $\bmod 10^9+7$ での逆元を求めることができるようになりました。

おわりに

ここでは、剰余演算で逆元を求める方法について見てきました。フェルマーの小定理を使えば、 $a$ の逆元は $a^{p-2}$ となることがわかるので、これを繰り返し二乗法を用いて求めればいいのでした。ここで見た内容を応用すれば、別のページで見るように、 ${}_n\mathrm{C}_k$ を $10^9+7$ で割った余りを計算することもできるようになります。