数ならぬ

理学系のこと、特に数学について書きます。雑学的な知識もまとめていく所存。

ウィルソンの定理とその一般化

　 $Wilson$ の定理というものがある。この定理は階乗についての合同式で、次のような形である。

$Wilson$ の定理

$p$ を素数とする。

$(p-1)!\equiv -1\hspace{2mm}(mod\hspace{2mm} p)$

証明は逆元の性質を使ったものになる。

$Proof$

証明に本格的に入る前に以下の補題を示す。

$x^2\equiv 1\hspace{2mm}(mod\hspace{2mm}p)$

$\Longleftrightarrow x\equiv\pm1\hspace{2mm}(mod\hspace{2mm}p)$

$Proof$

因数分解のように式を変形すると、 $x^2\equiv 1\hspace{2mm}(mod\hspace{2mm}p)$

$\Longleftrightarrow (x-1)(x+1)\equiv0$

$mod\hspace{2mm}p$ で、整数には逆元が存在する。よって $x\equiv\pm1\hspace{2mm}(mod\hspace{2mm}p)$ $◽︎$

この補題をうまく用いると $Wilson$ の定理は簡単に示される。この補題の主張しているのは自乗して $1$ となるような数は $\pm1$ のみであるということであるので、逆に言えば他の数では逆元は自身と一致しない。 $1\times2\times3\times\cdots\times (p-1)$ について法を $p$ とした合同式を考える。 $p=2$ の時、題意の合同式は満たされるので、 $p$ を奇素数として考えても良い。ここで、 $1,p-1$ 以外の数は他の数と対消滅する。 $p=7$ の例がわかりやすい。

$p=7$ の例

$1\times 2\times 3\times 4\times 5\times 6$ から $1,6$ を抜き去ったものを考える。 $2\times 3\times 4\times 5=\underline{2\times4}\times\underline{3\times5}$

下線部は全て $1$ に $7$ を法としたとき合同であるので $6!\equiv 6\times 1\equiv -1\hspace{2mm}(mod\hspace{2mm}7)$

よってこれを一般化した議論により、 $(p-1)!\equiv (p-1)\cdot 1\equiv -1\hspace{2mm}(mod\hspace{2mm}p)$ $◽︎$

　これをさらに一般化したのが次の定理である。

素数冪についての $Wilson$ の定理

$p$ を奇素数とする。このとき $P(n)$ を $n$ と互いに素な全ての正整数の積と定義すると、正整数 $e\ge 1$ に対して

$P(p^e)\equiv -1\hspace{2mm}(mod\hspace{2mm} p^e)$

例

$P(9)=1\times2\times4\times5\times7\times8$

$=2240\equiv -1\hspace{2mm}(mod\hspace{2mm}9)$

$P(25)=1\times2\times3\times4\times6\times7\times8\times9$

$\times11\times12\times13\times14\times16\times17\times18\times19$

$\times21\times22\times23\times24$

$=41,363,226,782,215,962,624\equiv -1\hspace{2mm}(mod\hspace{2mm}25)$

定理を証明する前に次の補題を証明する。

素数冪の方程式

$p$ を奇素数、 $e$ を正整数とする。このとき、

$x^2\equiv 1\hspace{2mm}(mod\hspace{2mm}p^e)\Longleftrightarrow x\equiv\pm1\hspace{2mm}(mod\hspace{2mm} p^e)$

$Proof$

証明はリンク先を参照せよ $◽$

この補題は $Wilson$ の定理の証明中に示した補題の素数冪への一般化となっている。この補題を使うと一般化した $Wilson$ の定理は簡単に示される。

$Proof$

素数冪についての $Wilson$ の定理を示す。

$P(n)$ について、この積を、自身とは異なる逆元を持つ元と、自身を二乗すると $1$ となる元の積にわけて考える。

ここで、自身とは異なる逆元を持つ元の逆元はもともとの元に一致するので、互いに打ち消しあってこの部分の積は $1$ となる。

自身を二乗すると $1$ となる元は補題によって $1,p^e-1$ しか存在しないので、合同式は $-1$ となる。

この二つの事実を掛け合わせると、 $P(n)\equiv -1\hspace{2mm}(mod\hspace{2mm}p^e)$ がわかる $◽︎$

証明としては意外と単純である。打ち消しあって $1$ となる部分が大きかったのがこの成功の立役者である。あとは他の残った二元の合同式を使えば簡単に示される。