■階乗の整除性(その5)

連続するk個の自然数の積

  n(n−1)・・・(n−k+1)

がk!で割り切れることは

  n(n−1)・・・(n−k+1)/k!

が整数であることがいえればよいのであるが,

  n(n−1)・・・(n−k+1)/k!=nCk

すなわち,二項係数はその定義から組み合わせの総数=整数であるから明らかであろう.しかしながら,このことを証明しようとするとかなり厄介である.

 nの倍数は連続するn個の自然数ごとに1個存在するから,連続するk個の自然数n〜n−k+1までの間に2の倍数は少なくとも[k/2]個,3の倍数は少なくとも[k/3]個,・・・

 しかし,

  n(n−1)・・・(n−k+1)

がk!で割り切れることは,加法・乗法・除法に関わる定理としてみると決して自明ではない.実際,ガウスやディリクレは純粋に算術的な証明を与えようとして悪戦苦闘したと伝えられている.算術の難しい定理も,組み合わせ論の視点からみれば易しい定理であることはあり得るのである.

===================================

[Q]n^5−nは10の倍数であることを示せ.

[A]n^5−n=n(n^4−1)=n(n^2−1)(n^2+1)

=(n−1)n(n+1)(n^2+1)

 (n−1)n(n+1)は3個の連続する整数の積であるから3!=6で割り切れることはわかるが,(n^2+1)は

  2,5,10,17,26,・・・

となって,n^5−nが10の倍数であるかどうかはよくわからない.

 そこで,数学的帰納法を使ってみよう.

P(1)=1^5−1=0・・・10の倍数である

P(k)=k5−kが10の倍数であると仮定する.このとき,

P(k+1)=(k+1)^5−(k+1)

=(k^5−k)+5k(k+1)(k^2+k+1)

 k(k+1)は2の倍数であるから,(k^5−k)も5k(k+1)(k^2+k+1)も10の倍数である.→P(k+1)は10の倍数である.

===================================