二項係数の最大公約数

二項係数を C(n,k) で表す。 ( C(n,k) ≡ n!/((n-k)!k!) )

・定理. C(p^n,1),...,C(p^n,p^n-1) の最大公約数は p
(pを素数,nを自然数)

C(p^n,1) = p^n なので、最大公約数は pのべきになる
従って各k(=1,...,p^n-1)に関して C(p^n,k) の pの因数の最小個数が s ならば。
最大公約数は p^s となる。

・階乗数 n! の 素数 p の因数個数は [n/p]+[n/p^2]+[n/p^3]+...
ここで [x] はガウス記号で、xを超えない最大整数を表す。

これを用いると C(p^n,k) = (p^n)! / ( (p^n-k)!k! ) の素数pの因数個数が計算できる
[p^n /p ] + [p^n / p^2] + [p^n / p^3] + ... - [p^n / p^n]
- [(p^n-k) /p ] - [(p^n-k) /p^2] - [(p^n-k) /p^3] -... - [(p^n-k) /p^n]
- [k /p ] - [k /p^2] - [k /p^3] - ... - [k /p^n]
= p^(n-1) + p^(n-2) + p^(n-3) + ... + 1
- [p^(n-1) - k/p] - [p^(n-2) - k/p^2] - ... - [1-k/p^n]
- [k /p ] - [k /p^2] - [k /p^3] - ... - [k /p^n]

・ここで(n≧r)を満たす整数n,実数rに対する, n-[n-r]-[r] に関して以下が言える。
rが整数のとき n-[n-r]-[r] = n-n+r-r = 0
rが整数でない時 n-[n-r]-[r] = n-[n-[r]-1+1+[r]-r]-[r] = n-(n-[r]-1)-[r]=1
(1>1+[r]-r>0を用いた)

これを用いると前式が計算できる
前式 = k/p^i が整数でないような、自然数iの場合の数 ( 1≦i≦n )
= n - kに含まれる因数pの個数
これは k = p^(n-1) によって最大化される (k は 1からp^n-1の間の自然数から選べる)
その時の値は n - (n-1) = 1 となる

従って C[p^n,k] の因数pの個数が最小になるようなk (k=1,2,3,...,p^n-1)は k=p^(n-1) であり、因数個数は1

以上から
C(p^n,1),C(p^n,2),...,C(p^n,p^n-1) の最大公約数は p になる。