Problem 160に少し出てくるので考えてみました。
Wilsonの定理は、
pが素数なら(p - 1) ! ≡ -1
です。これは、pを法とした既約剰余類群の元を全て掛け合わせると-1となる、とも言えます。その積をP(p)と書くことにします。例えばp = 7として
P(7) = 1 * 2 * 3 * 4 * 5 * 6 = 720 ≡ 6 ≡ -1 (mod 7)
です。では、素数以外を法とした既約剰余類群の元を全て掛け合わせるとどうなるでしょう。これが本稿のお題です。
例えば、n = 9を法とすると、
P(9) = 1 * 2 * 4 * 5 * 7 * 8 = 2240 ≡ 8 ≡ -1 (mod 9)
となります。一般にpを奇素数とすると、peを法とした既約剰余類群は巡回群になります。そうすると、自乗して1になるのが±1で、その他は掛け合わせて1になるペアになるので、結局全部掛け合わせると-1になるわけです。
P(9) = 1 * 8 * (2 * 5) * (4 * 7) ≡ 1 * (-1) * 1 * 1 ≡ -1 (mod 9)
2のべき乗は事情が違ってきます。計算してみると4の場合だけ-1で、あとは1になるようです。
P(4) = 1 * 3 = 3 ≡ -1 (mod 4)
P(8) = 1 * 3 * 5 * 7 = 105 ≡ 1 (mod 8)
なぜこうなるのでしょうか。P(8)をもう一度考えてみましょう。
P(8) = 1 * 3 * 5 * 7 = P(4) * (4 + 1) * (4 + 3)
= P(4) * (-3) * (-1) ≡ P(4) * P(4) * (-1)8/4 ≡ 1 (mod 8)
となります。n = 8以上なら上の8/4のところが必ず偶数になるから(-1)n/4 = 1となって、結局P(n/2)2だけ残るわけです。よって8以上の2のべき乗なら1になります。
まとめると、
nが素数べきのとき、8以上の2のべきなら、
P(n) ≡ 1 (mod n)
そうでないなら
P(n) ≡ -1 (mod n)
ここから素数べき以外の合成数について考えます。まずはn = 2p (pは奇素数)。
P(6) = 1 * 5 = 5 ≡ -1 (mod 6)
P(10) = 1 * 3 * 7 * 9 = 129 ≡ -1 (mod 10)
-1になるようですね。まずmod pで考えます。そうすると、積にpの既約剰余類群の元が1回ずつ出てくることがわかります。
P(10) = 1 * 3 * 7 * 9 ≡ 1 * 3 * 2 * 4 ≡ -1 (mod 5)
2を法とすると1なので、結局mod nでは-1となります。
n = 2ep (e ≥ 2)のときは、mod pで考えるとpの既約剰余類群の元が2e-1回、すなわち偶数回出てくるので1、mod 2eで考えると、p - 1回出てくるので1、よってnでも1になります。
次にn = pq (p, qは奇素数)の場合を考えてみましょう。同様にmod pで考えて、pの既約剰余類群の元がq - 1回現れるから1、mod qでも同じだから結局1になります。
まとめると、
2つの素数からなるとき、
n = 2p
P(n) ≡ -1 (mod n)
そうでないなら
P(n) ≡ 1 (mod n)
3つ以上の素数からなるとき、n = peqfrgとすると、peの法で考えて、peの既約剰余類群の元はqf-1(q - 1)rg-1(r - 1)だから偶数になります。よって、積は1になります。
最後に全てまとめると、
nが2e (e ≥ 3)以外の素数または素数べきのとき、2pのとき
P(n) ≡ -1 (mod n)
そうでないとき
P(n) ≡ 1 (mod n)
