『コンビネーションと素因数』

『コンビネーションと素因数』解答

◆宮城県　甘泉法師さんからの解答。

【問題１】

a=[a]+α、b=[b]+β　α，β＞０と記すと

[a+b] = [[a]+[b]+α+β] ≧ [[a]+[b]] = [a] + [b]

（証明終）

◆大阪府　macsyma2e さんからの解答。

【問題２】

(1)
0＜r＜p^l ⇒ 0＜r,p^l-r＜p^l 故

ord_p( C(p^l,r) )
＝ ∞
Σ
i=1 {[ p^l
pⁱ ]-[ p^l-r
pⁱ ]-[ r
pⁱ ]}

≧[ p^l
p^l ]-[ p^l-r
p^l ]-[ r
p^l ]

＝１

(2)
( 0＜r＜n ⇒ p|C(n,r) ) ⇒ ( n=p^l for some positive integer l )
を示す．

n=C(n,1) 故 n=qp^l and gcd(p,q)=1 for some positive integer q,l

であるが、
もし、q＞1 とすると 0＜p^l＜n となり p|C(n,p^l)．

然るに
ord_p( C(n,p^l) )
＝ ∞
Σ
i=1 {[ qp^l
pⁱ ]-[ qp^l-p^l
pⁱ ]-[ p^l
pⁱ ]}

i≦lの部分では [　] 内が何れも整数故 {　}=0、

i＞lの部分では [ p^l
pⁱ ]=0であり、

もし、[ qp^l
pⁱ ] ＞ [ qp^l-p^l
pⁱ ]
つまり
qp^l
pⁱ ≧k＞ qp^l-p^l
pⁱ for some integer k
とすれば
q≧kp^i-1＞q-1 なので q=kp^i-1 であるが、
これは gcd(p,q)=1 に反する．

注：【問題２】(2)の問題文では、f=n で終りです．

【青木コメント】

出題者の方からの申し出で、「条件1≦f≦n-1を満たす」を問題に追加しました。

【問題３】

(1) C(n,0)=C(n,n)=1 故 0＜r＜n とする．

ord_p( C(up^l-1,r) )
＝ ∞
Σ
i=1 {[ up^l-1
pⁱ ]-[ up^l-1-r
pⁱ ]-[ r
pⁱ ]}

i＞lの部分では
up^l-1-r,r＜up^l-1＜up^l＜p^l+1≦pⁱ 故
何れの [　]=0、

i≦lの部分では
r=apⁱ+b and 0≦b＜pⁱ for some integer a,b

であり、

up^l-1-r
=(up^l-i-a)pⁱ-1-b
=(up^l-i-1-a)pⁱ+pⁱ-1-b

なので、0≦pⁱ-1-b＜pⁱ に注意して

[ up^l-1-r
pⁱ ]+[ r
pⁱ ]

＝up^l-i-1-a + a

＝up^l-i-1

＝[ up^l-1
pⁱ ]．

(2) n≦p の場合は見易い故 p＜n の場合即ち

( 0≦r≦n ⇒ ￢( p|C(n,r) ) ) ⇒( n=up^l-1 and u＜p for some positive integer u,l )

を示す．

￢( p|C(n,1)=n ) 故

p^m≦vp^m＜n=(v+1)p^m-w＜(v+1)p^m≦p^m+1 for some positive integer m,v,w

であるが、もし、w＞1とすると

ord_p( C(n,p^m-1) )
＝ ∞
Σ
i=1 {[ n
pⁱ ]-[ n-p^m+1
pⁱ ]-[ p^m-1
pⁱ ]}

≧[ (v+1)p^m-w
p^m ]-[ vp^m-w+1
p^m ]-[ p^m-1
p^m ]

＝v - (v-1)
＝１

◆大阪府　macsyma2e さんからの解答。

【問題４】

G:=gcd( C(n,1),...,C(n,n-1) )．

【前半】

n=p^l for some positive integer l

のとき、【問題３】(1) により
p | G | C(n,1)=p^l.

l＞1ならば

ord_p( C(p^l,p^l-1) )
＝ ∞
Σ
i=1 {[ p^l
pⁱ ]-[ p^l-1
pⁱ ]-[ p^l-p^l-1
pⁱ ]}

i＞lの部分では何れの[　]内もより小さな正数、
i＜lの部分では何れの[　]内も整数．

＝ [ p^l
p^l ]-[ p^l-1
p^l ]-[ p^l-p^l-1
p^l ]

＝1 - 0 - 0
＝1

【後半】

G＞1 ⇒ ( n=q^m for some positive integer m, prime q )
を示せばよいが、それはGの任意の素因数qに対して
0＜r＜n ⇒ q | C(n,r) 故【問題３】(2) の証明のp,lをq,mに置き換えればよい．

注：pは最初に固定された素数なので、【後半】の問題文では、 p以外の任意の素数の累乗がnの反例となります．

　『コンビネーションと素因数』へ

　数学の部屋へもどる