数学オリンピック / 数論

Wilsonの定理

Wilsonの定理は、素数と階乗をつなぐ定理です。実用的な素数判定には重いですが、合同式の見方を深めるのに役立ちます。

定理

\(p\) が素数なら

(p-1)!\equiv-1\pmod p

が成り立ちます。逆も真で、この式が成り立つとき \(p\) は素数です。

証明を見る

\(1,2,\dots,p-1\) の各数は \(p\) を法として逆元を持ちます。自分自身が逆元になるのは \(x^2\equiv1\pmod p\) を満たす \(x\equiv1,-1\) だけです。

それ以外は \(x\) と \(x^{-1}\) をペアにでき、それぞれの積は \(1\) です。したがって全部の積 \((p-1)!\) では \(1\) と \(p-1\equiv-1\) だけが残ります。

(p-1)!\equiv1\cdot(-1)\equiv-1\pmod p

「\((n-1)!\equiv-1\pmod n\) なら \(n\) は素数」という判定ができます。ただし \((n-1)!\) が大きすぎるので、計算としては普通使いません。

\(6!\) を \(7\) で割った余りを求めます。

\(7\) は素数なので \(6!\equiv-1\equiv6\pmod7\)。

\(10!+1\) は \(11\) で割り切れるか調べます。

\(10!\equiv-1\pmod{11}\) より \(10!+1\equiv0\pmod{11}\)。割り切れます。

\((p-2)!\pmod p\) を \(p\) 素数で求めます。

Wilsonより \((p-1)(p-2)!\equiv-1\pmod p\)。\(p-1\equiv-1\) なので \((p-2)!\equiv1\pmod p\)。