■パスカルの三角形の概3等分(その5)

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

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

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

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

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

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

すなわち,組み合わせの総数=整数であるから明らかであろう.

 pを素数,mを自然数とするとき,

  (p^m,p^m-1)=p mod p^2

  (p^m+n-2,k)=(p^n-1,l) mod p^n

     k=p^m-1l,l=0,1,・・・,p^n-1のとき

  (p^m+n-2,k)=0 mod p^n  (それ以外)

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

【1】二項係数の整除性

[1]リュカ(1872年)

pを素数,0≦q<p,0≦r<pとする.

(pn+q,pk+r)=(n,k)(q,r) mod p

[2]ヤコブスタール(1952年)

pを素数,p≧5とする.

(pn+q,pk+r)−(n,k)=0 mod p^3

[3]クペルベルグ(1999年)

pを素数,(2p,p=(2,1)=0 mod p^4とする

(pn,pk)=(n,k) mod p^4

[4]シュワルツ(1959年)

pを素数,p≧5とする.

(p^2,p)=(p,1)=0 mod p^5

[5]ツイーヴ(2000年)

pを素数,p≧5とする.

(np^m,kp^m)=(np^m-1,kp^m-1) mod p^3m

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