本記事では，数学検定1級で頻出のトピックについてまとめていきます。
初学者の分かりやすさを優先するため，多少正確でない表現が混在することがあります。もし致命的な間違いがあればご指摘いただけると助かります。
ウィルソンの定理
$2$以上の整数$p$について，
(p-1)! \equiv -1\pmod p\label{main}
\end{align}
が成り立つことと$p$が素数であることは必要十分である。
証明
「$(p-1)! \equiv -1\pmod p$」$~\Rarr~$「$p$は素数」
$p$が素数でないならば，$(p-1)!$には$p$の約数がすべて含まれているため，$(p-1)!$を$p$で割った余りは$0$となります。この命題の対偶を取れば，$(p-1)!$を$p$で割った余りが$0$でないならば，$p$は素数となります。$(p-1)!$を$p$で割った余りが$0$でない一例として$(p-1)!$を$p$で割った余りが$-1$のケースがありますので，式($\ref{main}$)を満たすならば$p$は素数であることが示されました。
「$p$が素数」$~\Rarr~$「$(p-1)! \equiv -1\pmod p$」
$p{=}2$のときは$(2{-}1)!{=}1{\equiv}-1$で題意は満たされます。$p{\geq}3$のとき，$(p{-}1)!$から$2$つずつペアを作り，その積のほとんどが$\bmod p$で$1$であれば都合が良いと考えます。ある整数$m$に対して
m,2m,\ldots,(p-1)m
\end{align}
を$p$で割った余りはすべて異なるため，$mn{=}1$となる$n$が$1$から$p{-}1$の間にただ$1$つ存在します。
$n{\neq}m$のときは異なる$2$つの数のペアとなりますが，$n{=}m$のときはペアを作っていることにはなりません。このような$n$は$n^{2}\equiv 1\pmod p$を満たすため，$n=\pm 1$となります。すなわち，$n{=}1,p{-}1$のときは異なる$2$つの数のペアを作ることはできず，$(p{-}1)!$から$2$つずつペアを作ると$(p-3)/2$組のペアができることが分かりました。
以上より，$p{\geq}3$のとき$p$は奇数であることに注意すると，
(p-1)!
&\equiv 1\cdot \{2\cdot 3\cdots (p-2)\}\cdot (p-1)\\[0.7em]
&\equiv 1\cdot 1^{(p-3)/2} \cdot (p-1)
\equiv p-1
\end{align}
が得られるため，$p$が素数ならば式($\ref{main}$)を満たすことが示されました。
例題
$p=101$に対し，次の値を求めなさい。
\frac{(p-2)!}{2}\pmod p
\end{align}
$p=101$は素数であるため，ウィルソンの定理より
(101-1)!=100!\pmod{101}
\end{align}
が成り立ちます。ここで，
(p-2)! = 99! = 100!\cdot 100^{-1}\pmod{101}
\end{align}
を求めたいため，$\bmod p$における$100$の逆元$x$を求めます。$x$は
100x \equiv 1\pmod{101}
\end{align}
を満たすので$x=-1$となります。これを利用すれば，
(p-2)! = 100!\cdot 100^{-1} \equiv -1\cdot -1 \equiv 1\pmod{101}
\end{align}
が得られます。すると，与式は
\frac{(p-2)!}{2}\equiv \frac{1}{2} \equiv 2^{-1}\pmod p
\end{align}
と変形できるため，与式の値を求める操作は$\bmod p$における$2$の逆元を求める操作と等価です。先ほどと同様に，$2$の逆元$y$は
2y \equiv 1\pmod{101}
\end{align}
を満たすので，$y=51$となります。したがって，求める答えは$51$となります。
コメント