swk's log

* n^n が n! で割り切れない理由 [misc]

音楽シャッフル・クイズ [2005-10-21-2] の解答編にコメントが追加されている．「n^n が n! で割り切れない」のはその通りなのだが，その根拠を「n が n-1 で割り切れないから」とするのは厳密ではない，という指摘．

なぜなら、一般にaがbで割り切れないからといって、 aのn乗がbで割り切れないとは限らないからです。

http://www.hyuki.com/d/200510.html#i20051023140000

ん? そうなの? …ああそうか．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! で割り切れることはない．

---

とかかな．剰余類で考えた方がきれいみたい．

* ドラえもんの中で傑作短編は? [dora]

• http://piza.2ch.net/ymag/kako/964/964642144.html

4 名前： 名無しさん＠お腹いっぱい。 投稿日： 2000/07/27(木) 05:15
  ボールに乗って

短編すぎ．