モジュラ逆数 - オタクof数理の共同ブログ

よねすけです。今回は整数論を少しかじってみるよ。

$p$ を有理素数とし、 $\gcd(a,p)=1$ の時、

$ax\equiv 1(\mod p)$
なる整数 $x$ がただひとつ存在することが一般に知られています。(証明は $x,x'$ が上の式を満たすとして $x\equiv x'$ を示せる。)
このときの $x$ を $\mod p$ における $a$ の逆元(モジュラ逆数とも)と言い、 $x\equiv a^{-1}$ と書きます。
(競技プログラミングをしている友達がこのことについて質問してきました。競技プログラミングも結構数学を使うんだなあといった印象です。)

まあこれを書いただけじゃ意味が無いんでここでは１問問題を解いてみましょう。(本当はこの逆元を使ってウィルソンの定理を証明するのが良いんでしょうがここでは数オリ(?)の問題を載せます。)

正の整数 $a$ は
$1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{23}=\frac{a}{23!}$
をみたす。 $a$ を $13$ で割った余りを求めよ。

自分の数論の問題集を取り出したらこの問題にマークが付いてたのが懐かしいのぉ〜と思いましたね。もう４年も前ですね笑

早速解いていきましょう。右辺の $23!$ が邪魔なのでこれを払うと

$a=23!+\frac{23!}{2}+\cdots+\frac{23!}{23}$
となります。右辺の各項は整数で $\frac{23!}{13}$ 以外は $13$ で割れるので、
$\begin{eqnarray} a&\equiv&\frac{23!}{13}\\ &\equiv&12!\cdot 14\cdot 15\cdots 23\\ &\equiv&12!\cdot 10!\\ &\equiv&\frac{(12!)^2}{11\cdot 12}\\ &\equiv&\frac{(-1)^2}{(-1)(-2)}\\ &\equiv&2^{-1}\\ &\equiv&7 \end{eqnarray}$
となり、答えは $7$ と分かりました。
一応説明しておくと
$12!\equiv -1(\mod 13)$
としました。これはウィルソンの定理 - Wikipediaを用いました。
あと、
$2^{-1}\equiv 7(\mod 13)$
としましたが、確かに
$2\times7=14\equiv 1(\mod 13)$
を満たすので $2$ の $\mod 13$ における逆元が $7$ であることが分かりますね。

それでは。