■オイラーのトーシェント関数(その17)

 二項係数の中央の値

  cn=2nCn=(2n)!/(n!)^2

を考えます.あるいはもっと一般に,連続するk個の自然数の積

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

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

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

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

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

これらが整数であることは組み合わせの総数=整数であるから明らかでしょう.

 カタランの定数の整除性

  cn=2nCn/(n+1)=2nCn−2nCn+1

はまだいいとしても,

  ck=((k+1)^2)!/(k^2)!・(k+1)^2・・・(2k)^2・(2k+1)

の整除性を証明するにはどうしたらよいでしょうか?

 

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

【1】対応する不等式

 たとえば,

  Q=(6n+2)!n!/(3n+1)!{(2n)!}^2

が整数であることを証明するには,この式に対応するガウス記号[・]を用いた不等式

  [(6n+2)/m]+[n/m]≧[(3n+1)/m]+2[2n/m]   m≧2

が成立するかどうかを調べる.

 成立することがわかれば,任意の素数pに対して

  (Qの分子がpで割り切れる回数)−(Qの分母がpで割り切れる回数)≧0であることを示せばよい.

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

【2】素因数の累乗の評価

[1]n!を素因数分解したとき,ある素数pがp^rの形で含まれていたとすると,ガウス記号[・]を用いて

  p=[n/p]+[n/p^2]+・・・+[n/p^s]+・・・

[2]cn=2nCnを=(2n)!/(n!)^2

を素因数分解すると,√2nより大きい素数は現れてもp^1の形である.それ以下の素数がp^kの形で現れれば,p^k≦2nである.

(証明)この式に対応する不等式

  [2n/p^s]−2[n/p^s]

は0か1であることよりQED.n/p^sの小数部分が0.5未満ならば0,0.5以上ならば1であることを具体的に確かめてみるとよい.

 すなわち,素因数分解するとnより大きく2n以下の素数があれば,それらはすべて1乗の形の積として現れます.もしもその間に素数がなければ,n以下の素数の積で表されるはずです(実はさらに2n/3以下の素数の積なります.2n/3より大きくn以下の素数は分子に2回,分母に2回現れて約分される).

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