82. mod 逆元の算出方法とフェルマーの小定理について

昨日のABC F問題のように、既約分数（有理数）を「(mod 素数) における逆元を用いて整数として表現する」ことが問われる場合があります。

atcoder.jp

この記事では

分数をなぜ整数として表現できるのか
どうやってその値を算出するのか

という辺りを丁寧にまとめてみます。

逆数と逆元（数学的に丁寧な話）

この項目は数学的に込み入った話になるので、プログラミング的な話に注目する人は飛ばしても良いです。

まず、分数とは何かをあらためて考えてみます。 $a \in \mathbb{R}\backslash\{0\}$ ， $b \in \mathbb{R}$ について、

$\displaystyle \frac{b}{a} = b \times \frac{1}{a}$

です。言い換えれば、分数（＝除算）は割る数 $a$ の逆数 $\displaystyle \frac{1}{a}$ を掛ける操作（＝乗算）です。

では、逆数とは何でしょう。 $a \in \mathbb{R}\backslash\{0\}$ の逆数を $a^{-1}$ と表現すると、逆数 $a^{-1}$ は以下の性質を満たすものと定義されます。

$a \times a^{-1} = 1$

ここまでは算数の話ですが、この逆数の概念を深掘って考えてみます。

まず、「掛けて 1 になる」という性質に注目します。この 1 という数は特殊な数で、 $a \in \mathbb{R}$ について以下の性質が成り立ちます。

$a \times 1 = 1 \times a = a$

当たり前ですが、どのような実数と 1 を掛け合わせてもその数は変化しません。これを少し抽象化して表現すると、「1 は、ある二項演算を適用した結果、相方を変化させない元（＝数）である」といえます。このような性質を持つ元を、「ある二項演算における単位元」といいます。たとえば、実数について「1 は乗算における単位元」といえます。

以上のことから、「 $a$ の逆数 $a^{-1}$ 」を抽象化して表現すると、「 $a$ に乗算を適用した結果、単位元となるような元」といえます。このような元を、「乗算における逆元」といいます。

以下、単に「単位元」「逆元」というときは「乗算における」元であると理解してください。

…余談ですが、この辺りの話は群論と深く関わっています。興味のある方は調べてみてください。

逆数と逆元（結論）

ここまでの話から、自然数 $n$ を考えると、「 $n \times n^{-1} = 1$ を満たす $n^{-1}$ は、 $n$ の逆元（逆数）である」といえます。

また、素数 $p$ を法とする自然数 $n \lt p$ を考えると、「 $n \times n^{-1} \equiv 1 \pmod p$ を満たす $n^{-1}$ は $n$ の逆元である」といえます。

以上のことから、「自然数における逆数を、 $p$ を法とする逆元として表現する」ことで、整数として有理数を扱えるイメージがわかるかと思います。

具体例を考えます。有理数 $\displaystyle \frac{3}{4}$ を $7$ を法とする整数で表現します。

$\displaystyle \frac{3}{4} = 3 \times 4^{-1}$

であり、 $4^{-1} \equiv 2 \pmod 7$ です（ $4 \times 2 \equiv 1 \pmod 7$ となるため）。

よって、

$3 \times 4^{-1} \equiv 3 \times 2 \equiv 6 \pmod 7$

となり、6 と表現できることがわかりました。

ここで問題となるのが、「mod 逆元をどうやって求めるのか？」ということです。先ほどの例のように mod 7 程度であれば順番に確認すればよさそうですが、実際には巨大な数が法となるためもっと効率よく調べる必要があります。

実は、素数 $p$ を法とする場合、 $\displaystyle n^{-1} \equiv n^{p-2} \pmod p$ であることが知られています。

この事実について詳しく掘り下げてみます。

フェルマーの小定理

先ほどの事実を証明するにはフェルマーの小定理が重要となってきます。

【フェルマーの小定理】
素数 、自然数  に対して、

フェルマーの小定理が示せれば、 $\displaystyle n \times n^{p-2} = n^{p-1} \equiv 1 \pmod p$ となるので、 $\displaystyle n^{p-2}$ が $n$ の逆元であることを示せたことになります。

フェルマーの小定理の証明は色々あるのですが、数学的帰納法を使ったものを紹介しておきます。

【証明】
素数 、自然数  に対して、 を示す。
これを示せれば、両辺を  で割って  がわかる。

①  のとき、明らかに 。
② 二項定理より、


※シグマの中身ですが、 が素数であることと、
  Combination の式を考えるとどの項も必ず  の倍数になることがわかり、
   を法とする場合  になります。

よって、 ならば 。

①②から数学的帰納法より全ての自然数  に対して 。
よって、フェルマーの小定理を示せた。（証明終わり）