2013年8月5日月曜日

Wilson の定理

Wilson の定理とは、素数 \(p\) に対し \((p-1)! \equiv -1 \bmod p\) が成り立つという初等整数論の定理である。 これが重要な定理ということは特にないと思うのだが、大体の教科書に載っている。 証明にはフェルマーの小定理を使ったり原始根を使ったりすることが多い。 しかし、そんな道具立ては解り易くないと思うのだ。

少し一般的な次のことを証明する (Gauss の一般化と呼ばれているようだ): \(n\) を \(3\) 以上の整数とするとき、\(\prod_{i \in \mathbb{Z}/n\mathbb{Z}^\times} i \equiv (-1)^k \bmod n\) が成り立つ。 ただし、\(k\) は \(1\) の平方根の個数の半分。

(証明) \(\mathbb{Z}/n\mathbb{Z}^\times\) は群なので、各元に逆元が存在する。 自分自身が逆元である元以外は、\(a\) と \(a^{-1}\) が別々に存在して \(a\cdot a^{-1} \equiv 1 \bmod n\) だから積に寄与しない。 自分自身が逆元である元とは \(a^2 \equiv 1 \bmod n\) ということなので、\(1\) の平方根である。 このような元 \(a\) に対し、\(-a\) も同様に \((-a)^2 \equiv a^2 \equiv 1 \bmod n\) を満たす。 \(n\) は \(3\) 以上と仮定したので、 \(a\) と \(-a\) は等しくない。 この二つの元の積を考えると、\(a\cdot(-a) \equiv -a^2 \equiv -1 \bmod n\) である。 \(1\) の平方根を \(2\) 個ずつ組にしたので、\(k\) を \(1\) の平方根の個数の半分として \(\prod_{i \in \mathbb{Z}/n\mathbb{Z}^\times} i \equiv (-1)^k \bmod n\) が成り立つ。 (証明終わり)

元の形の Wilson の定理は、奇素数 \(p\) に関しては \(n=p\) として上の命題を適用すれば \(\mathbb{Z}/p\mathbb{Z}\) が体だから \(a^2 \equiv 1 \bmod p\) の解は \(\pm 1\) 以外にないことから従い、\(p=2\) の場合は \(1 \equiv -1 \bmod 2\) なので成り立つことが判る。

さて残りは \(1\) の平方根の個数を確定すれば話が完結するが、これは \(\mathbb{Z}/n\mathbb{Z}^\times\) を巡回群の直積で書いたときの直積因子の個数を \(m\) とおくと、\(2^m\) となる。 したがって、素数以外には \(n = 4, p^e, 2 p^e\) の時だけ右辺が \(-1\) になる。 ちなみにこの右辺の値の数列がA103131としてOEISに登録されている、といった情報がMathWorldに書いてあった。