代数学 証明

この問題の証明が分かりません。
分かる方、早急にお願いします。

【問】　素数p、任意の自然数ｑ、ｒについて、

　　　　p^r*q C p^r　がｐの倍数でないことを証明せよ。

No.1 回答者： noname#152422 回答日時： 2011/11/28 20:47

> p^r*q C p^r　

この式の意味は何ですか？

この回答への補足

分かりにくくてすみません。


　｛q　×　p^r｝Ｃ｛p^r｝


【補足】
（１）^rはr乗のこと
（２）Ｃはコンビネーションのこと
を表してます。

これで分かりますでしょうか?
宜しくお願いします。

補足日時：2011/11/28 21:11

No.2 回答者： FT56F001 回答日時： 2011/11/28 21:41

力任せだけれど，次のように示せそうです。

[補題]
pを素数とする。qがpの倍数でない時，階乗(q*p^r)!　を素因数分解したpの指数は
q*(1+p+p^2+p^3+・・・+p^(r-1))=q*{(p^r)-1}/(p-1)である。

[補題の証明]
1,2,・・・,qp^rまでに
pの倍数は，p,2p,3p,・・・,qp^(r-1)*pのq*p^(r-1)個である。
p^2の倍数は，p^2,2p^2,3p^2,・・・,qp^(r-2)*p^2のq*p^(r-2)個である。
p^3の倍数は，q*p^(r-3)個である。
・・・・
p^(r-2)の倍数は，q*p^2個である。
p^(r-1)の倍数は，q*p個である。
p^rの倍数は，p^r,2p^r,・・・,qp^rのq個である。

よって，
1,2,・・・,qp^rまでに
p^rの倍数はq個，
p^(r-1)の倍数でp^rの倍数でないものは，q(p-1)個，
p^(r-2)の倍数でp^(r-1)の倍数でないものは，q(p^2-p)=q(p-1)*p個，
・・・
p^(k-1)の倍数でp^kの倍数でないものは，q(p-1)*(p^(r-k))
・・・
p^2の倍数でp^3の倍数でないものは，q(p-1)(p^(r-3))個
pの倍数でp^2の倍数でないものは，q(p-1)(p^(r-2))個

よって，(q*p^r)!を素因数分解したpの指数は，
q(p-1)p^(r-2)+2*q(p-1)p^(r-3)+3*q(p-1)p^(r-4)+・・・+(r-1)*q(p-1)+r*q
=q{p^(r-1)-p^(r-2)+2p^(r-2)-2p^(r-3)+3p^(r-3)-3p^(r-4)+・・・+
(r-1)p-(r-1)+r}
=q{p^(r-1)+p^(r-2)+p^(r-3)+・・・+1)=q{(p^r)-1}/(p-1)
[補題の証明終わり]

さて，与式は組み合わせ(コンビネーション)nCm=n!/{m!(n-m)!}に
n=qp^r，m=p^rを代入した形である。
与式=(p^rq)C(p^r)=(q*p^r)!/{(p^r)!*((q-1)p^r)!}の
分子を素因数分解したpの指数=q{(p^r)-1}/(p-1)
分母を素因数分解したpの指数={(p^r)-1}/(p-1)　+　(q-1){(p^r)-1}/(p-1)
=q{(p^r)-1}/(p-1)
よって分子と分母のpの指数は同じであるため，与式全体のpの指数は0となる。
すなわち与式はpの倍数ではない。

No.3 回答者： FT56F001 回答日時： 2011/11/28 22:56

#2です。

自分の証明を見直してみると，勝手にq<pの条件をつけていました。

示せている補題は
「pを素数とする。q<pの時，階乗(q*p^r)!　を素因数分解したpの指数は
q*(1+p+p^2+p^3+・・・+p^(r-1))=q*{(p^r)-1}/(p-1)である。」
です。

元の問題は
「素数p、任意の自然数ｑ、ｒについて、p^r*q C p^r　がｐの倍数でない」
を主張していますが，これには反例があります。
p=3,q=3,r=1とすると「9C3は3の倍数でない」はずです。
しかし実際は9C3=9*8*7/(3*2*1)=84=3*28で3の倍数です。

示すべき問題には，
「素数p、任意の自然数ｑ、ｒ(ただしq<p)について、p^r*q C p^r　がｐの倍数でない」
か
「素数p、任意の自然数ｑ、ｒ(ただしqはpの倍数ではない)について、p^r*q C p^r　がｐの倍数でない」

のように付帯条件がつきませんか?
前者なら#2で証明できていそうです。
後者なら#2では不完全です。

この回答への補足

詳しくありがとうございます。

課題を出された段階では、そのような条件はありませんでしたが、
確かに反例の通り、このままだとおかしいですね。

もし後者の場合、どのような証明が考えられるでしょうか？
大学の教授が条件を書き忘れたとした場合、後者の方が有力なので、後者の証明が分かると大変助かります。

補足日時：2011/11/28 23:45

No.4 回答者： alice_44 回答日時： 2011/11/29 09:50

n = q(pのr乗) として、n の値を与えたとき、

r が一意に決まるか？ を考えれば、
後者の条件がついているのが自然でしょうね。
A No.2 の証明で、ちゃんと示せていますよ。

No.5 ベストアンサー 回答者： FT56F001 回答日時： 2011/11/29 10:12

Alice先生ありがとうございます。

#2でよいのか，いまいち不安なので，
「qはpの倍数でない」の付帯条件が付いた場合の証明を考えました。

コンビネーションnCm=n!/{m!(n-m)!}=Π[j=1→m](n-m+j)/jと書けます。
与式qp^r　C　p^r=Π[j=1→p^r]((q-1)p^r+j)/jとなります。ここで，
p^r個の因子，((q-1)p^r+j)/j　(j=1,2,3,・・・,p^r)を考えます。
与式がpの倍数なら，これらの因子の分子にpの倍数があるはずです。

分子がp^k(k=1,2,・・・r-1)で割り切れる時，jがp^kの倍数です。
分母もp^kで割り切れるため，与式を素因数分解したpの指数に，因子は貢献しません。
分子がp^rで割り切れる時はj=p^rの場合で，因子はqそのものです。
仮定によりqはpの倍数でないので，与式を素因数分解したpの指数に，因子は貢献しません。
よって，因子の中にpの倍数がないので，その積である与式もpの倍数ではありません。

この回答へのお礼

ありがとうございました!!
なんとか理解することができ、レポートも提出することができそうです。

本当にありがとうございました。

お礼日時：2011/11/30 01:17