概要

競技プログラミングをしていると、解答を「mod n で求めよ」と言われることがあります。
この制約のもとで割り算をする方法を学習したので、~~既に同じことを解説した記事が無数にあることとは思いますが~~自分のため、まとめてみようと思います。

mod n のもとで割り算はできない

そもそも、mod n のもとで計算をするのは、計算結果が大きくなりすぎないようにするためと、計算自体にかかる時間を削減するためです。
そのため、途中の計算の結果でも剰余を取って値を小さくしていきます。
この際、足し算・引き算・掛け算は通常通り計算した後にnの剰余を取れば良いです。

(8 + 2) mod 5  # 0
(8 - 2) mod 5  # 1
(8 * 2) mod 5  # 1

一般には、以下で表される $x, y$ について、

\displaylines{
x = pn + q \\
y = sn + t
}

和・差・積は

\displaylines{
x + y = (p + s)n + (q + t) \\
x - y = (p - s)n + (q - t) \\
x * y = (p * s)n + (q * t)
}

となることから、'$(x + y) \mod n$' と '$\lbrace (x \mod n) + (y \mod n)\rbrace \mod n$' が等しいことがわかります。
（引き算・掛け算も同様）

一方、 '$(x ÷ y) \mod n$' は一般に '$\lbrace(x \mod n) ÷ (y \mod n)\rbrace \mod n$' と異なるため、割り算ではそのまま計算することができません。

(8 / 2) mod 5          # 4
(8 mod 5) / (2 mod 5)  # 3 / 2 -> 1

この問題を解決するために、乗法の逆元を使用します。

ある数aの乗法の逆元とは「aに掛けると（乗法の単位元である）1になる数」のことを指します。
通常の実数上の掛け算では逆数 $\frac{1}{a}$ がこれに当たります。

「割り算をする」というのは、「逆元と掛け算をする」ことと同等であるということになります。
（小学校の時、「$÷a$」と「$×\frac{1}{a}$」が同じだと習いましたね。）

mod n の世界でも、aで割る際は代わりにaの逆元を掛ければ良いです。
すなわち、「aにかけたら1になる数」を掛ければ良いということです。
では、「aにかけたら1になる数」はいくつでしょうか？

剰余に関する定理に、フェルマーの小定理というものがあります。
証明は他のサイトに譲るとして（高校生でも理解できる証明があります）、内容は以下になります。

pを素数とし、aをpと互いに素な整数とすると、
a^{p-1} \equiv 1 \pmod p
が成り立つ

したがって、

a * a^{p-2} \equiv 1 \pmod p

であるため、$a^{p-2}$がaの逆元、ということになります。

以上から、mod n のもとでaで割るときは、$a^{n-2}$を掛ければ良いです。
（nが素数のときに限りますが、実際の問題の場合、nは何らかの素数として与えられているはずです。）

所謂modintで割り算が

# a ÷ b (mod p)
def div(a, b, p)
    inv = pow(a, p-2, p)    # a^(p-2) を pで割った余り
    return (a * inv) mod p

のように書かれるのは、上記の理由によります。

まったくの初学の段階では、モジュラ逆数とか言われたり実装を見たりしてもよく分からなかったので、調べた結果を~~アウトプットによる学習の意図が強いですが~~ mod n での除法についてまとめてみました。