フェルマーの小定理による逆元

加算、減算、乗算は modulus の下でもうまく扱えますが、通常の割り算はそうではありません。単純に割ってから余りを取ることはできません。⚠️

解決策は法逆元です。x で割ることを、x の逆元を掛けることに置き換えます。つまり、a / b mod m は a に b の逆元を掛ける計算になります。

x の逆元とは、modulus の下で x と掛けると 1 になる数です。通常の算術における 1/x の役割を果たします。

x と m が共通因子を持たない場合に限り、逆元が存在します。1e9+7 のような素数を法とする剰余を使えば、0 でないすべての x に逆元が存在することが保証されます。

フェルマーの小定理によると、素数 p に対して、x が p の倍数でない限り、x の p−1 乗は 1 と合同になります。

x の因子を1つ取り出すと、残りはその逆元でなければなりません。したがって、x の逆元は x の p−2 乗を計算し、p で割った余りになります。

この指数は非常に大きいため、前のレッスンで学んだ高速べき乗法を使います。Python では pow を1回呼び出すだけで、すべて処理できます。

mod の下で a を b で割るには、a に b の逆元を掛けます。その余りが、真の商を p で割った余りと正確に一致します。

0 に何を掛けても 1 にはならないため、0 の逆元は存在しません。modulus の下で 0 になる値で割らないように確認してください。

フェルマー法による逆元は高速べき乗を1回行うため、計算量は O(log p) です。数回の割り算なら安価ですが、何百万回も行うとそのコストが積み重なります。

多数の逆元が必要な場合は、要素ごとに pow を呼び出す代わりに、巧妙な線形パスであらかじめ計算します。次に学ぶ nCr でこれを利用します。

素数を法とするとき、法逆元を求めるには何乗すればよいでしょうか。

これで、素数を法とする剰余の下で、法逆元を掛けて割り算ができるようになりました。逆元は pow を使って x の p−2 乗として求めます。ただし、0 の逆元は決して求めないでください。✅