音楽シャッフル・クイズ [2005-10-21-2] の解答編にコメントが追加されている．「n^n が n! で割り切れない」のはその通りなのだが，その根拠を「n が n-1 で割り切れないから」とするのは厳密ではない，という指摘．
なぜなら、一般にaがbで割り切れないからといって、 aのn乗がbで割り切れないとは限らないからです。
ん? そうなの? …ああそうか．a = 6，b = 12 だとすると，a は b で割り切れないけど a^2 は b で割り切れるな．
うーむ，人の答えを見て納得したつもりになってただけだった．反省．
剰余類を持ち出さないならどうなるかな．
n^n が n! で割り切れるためには，n^n が n-1 で割り切れることが必要．そのためには，n-1 の任意の素因数 m (m>=2) が n の約数であることが必要．これは
h m = n - 1
g m = n
なる自然数 h, g が存在することと同値．n を消去すると
h m = g m - 1
よって
m = 1 / (g - h)
となる．m>=2 であるどんな整数に対しても，これを満たすような g, h は存在しない．だから結局どんな n に対しても，n^n が n! で割り切れることはない．
とかかな．剰余類で考えた方がきれいみたい．
最終更新時間: 2009-01-04 15:31