素数と組み合わせの問題

質問

Z会の問題なのですが、わからないところがあるので質問します。

nは素数pと自然数mを用いて、n=p^mと表される数であるとする。このとき、次の各問に答えよ。
(1)r=1,2,・・・,n-1のとき、nCrはpの倍数であることを示せ。
(2)nと(2^n)-1は互いに素であることを示せ。

nCrが自然数であることなら帰納法でなんとかなると思ったのですが、pの倍数になることがどうしても証明できません。どなたか教えてください。

回答No.1

kabaokaba · ベストアンサー

これはとても有名な問題です．
ある分野の数学は
この問題の(1)がベースの一つになってるくらいです

(1)
＃r=0またはnのときは
＃nC0=nCn=1なのでpの倍数ではない
＃これは解には関係ないけど大事な性質
m=1のとき
r=1,2,...,n-1のとき
nCrは（1より大きい）自然数であり
nCr = pCr
= p!/r!(p-r)!
= p・(p-1)・・・(p-r+1)/r!
ここでpは素数であり，rはp未満だから
r!の約数にはpの約数は存在せず
さらにnCr=pCrは自然数なので
結局，
(p-1)・・・(p-r+1)/r!
が自然数となり，
nCr= p・(自然数)でnCrはpの倍数

m>=1として
(a+b)^{p^m} のa^{p^m}とb^{p^m}以外の
項の係数がpの倍数であるとする

m+1のとき(n=p^{m+1})
X=a^{p^m}+b^{p^m}とおく．
(a+b)^{p^{m+1}}
=
((a+b)^{p^m})^p
=(X+ Σ(pの倍数)a^r b^{n-r})^p
帰納法の仮定よりこれは
X^p + (Σ(pの倍数)a^r b^{n-r})^p
+ Σ(pの倍数)X^k (Σ(pの倍数)a^r b^{n-r})^k
と表せる
さらに，X^pについても帰納法の仮定より
X^p
=
a^{p^{m+1}} + b^{p^{m+1}}
+ Σ(pの倍数)(a^{p^m})^s(b^{p^m})^{p-s}
と表せるので，
結局
(a+b)^(p^{m+1})
=a^{p^{m+1}} + b^{p^{m+1}}
+Σ(pの倍数)a^t b^{n-t}
と表せる．つまり
n=p^{m+1}に対して
nCrはpの倍数
したがって，任意の自然数mに対して
n=p^mとして
nCrはpの倍数

＃本当はもっとすっきり書けるんだけども
＃合同式を使っていいのかわからんので

(2)
2^n - 1 = (1+1)^n -1 = ΣnCr + 1
であり，n=p^m であるので(1)より
nCrはpの倍数
よって，2^n-1をpで割ると余りは1である
ここで，もし，p^k (k>=2)が2^n-1の約数であれば
当然，pも2^n-1の約数になるがこれはありえない．
したがって，p^k (k>=1)は2^n-1の約数ではない．
一方，n=p^mの約数は1以外はすべて p^k (k>=1)の形である．
よって，
nと2^n-1は互いに素である．

お礼

回答ありがとうございます。
合同式は習っていないので、上の解き方を投稿してくれてよかったです。
2つほど質問をさせてください。
(a+b)^{p^{m+1}}
=
((a+b)^{p^m})^p
の等式は上の式をどのように変形すればよいのでしょうか。(a+b)をp^m回掛けたものをさらにp倍して・・・とイメージで理解することはできたのですが、式変形で導くことができません。

それともう1つ、読んでいて思いついたのですが

nCr=n!/r!(n-r)!
=n(n-1)(n-2)・・・(n-r+1)/r!
=p・p^m-1(n-1)・・・(n-r+1)/r!
として、pは素数なのでr!と1以外の公約数は持たず
nCrが必ず自然数となることを考えると
p^m-1(n-1)・・・(n-r+1)/r!が自然数となり、pは必ず分母に残る

という証明では不備があるのでしょうか。

補足

お礼のところで
「pは素数なのでr!と1以外の公約数は持たず」
の部分が間違ってると気付きました。

回答No.4

kabaokaba

No.1です
＞という証明では不備があるのでしょうか。
あー，頭とけてるなぁ＞自分
それで十分ですね．

もう一個の方は
(a^m)^m = a^{mm} = a^{m^2}
で理解してください．
指数法則を組み合わせただけです．

解法としてはNo.2さんのがきれいでいいですね

ちなみに
＞nCrが自然数であることなら帰納法でなんとかなると思った
これはかなり簡単にできます．
nCr = n-1Cr + n-1Cr-1
を使えばほとんど自明です．

お礼

回答ありがとうございました。
答案ができたのでここらへんで締めます。

回答No.3

kabaokaba

No.1です．
＞「うまい」変形から導く方法もあります。

あー，この手がありますねえ
フェルマーの小定理と標数pの体の議論が
頭に出てきたので
二項定理で力技しちゃいました．

回答No.2

naniwacchi

「うまい」変形から導く方法もあります。
参考にしてみてください。

(1)
(n-1)Ｃ(r-1)= r/n* nＣrより、n* (n-1)Ｃ(r-1)= r* nＣrとなります。
この式の左辺は明らかに、n= p^mの倍数となっています。

右辺ですが、rが 1≦ r≦ n-1＜ p^mであることより、
rは pを因数にもつとしても最大 m-1個までしか持てないことになります。
（rを素因数分解しても、pは高々 p^(m-1)までしか含まない）

ということは、右辺の nＣrは少なくとも p^1= pを因数にもたなければならなくなります。
つまり、nＣrは pの倍数であることになります。

(2) #1さんが書かれているとおり、
2^n- 1= Σ[r= 1～n-1] nＣr+ 1となり、nＣrが pの倍数ですので、
2^n- 1= p* A+ 1・・・(1式)

の形に表されます。

ここで、n= p^mと共通の約数をもつと仮定します。
その約数は、p^k（1≦ k≦ m）と表すことができます。
これを(1式)に適用すると、
p* A+ 1= p^k* B
1= p* { p^(k-1)* B- A }

すると、「 1が pの倍数である」という矛盾した式になってしまいます。
背理法により、互いに素であることが示されます。

お礼

回答ありがとうございます。
お礼を書いている間に話が進んでいました。
こちらの方法でも解いてみます。