読者です 読者をやめる 読者になる 読者になる

オタクof数理の共同ブログ

京大情報学科数理工学コースの学生4人による共同ブログです

モジュラ逆数

よねすけ 数学 整数論

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

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

ax\equiv 1(\mod p)

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

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

正の整数a
1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{23}=\frac{a}{23!}

をみたす。a13で割った余りを求めよ。

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

早速解いていきましょう。右辺の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であることが分かりますね。

それでは。

広告を非表示にする