質問<1573>2004/1/27
RnCr=Nn-1Cr-1を用いて0×nC0+1×nC1+…n×nCnって どういうふうに考えるべきなんでしょうか?? あと、Fermatの定理というもの、二項定理とどんなふうにからんでくるの でしょうか?? 割り切れることを示す証明とか…
お便り2004/2/1
from=こんにちは
0×nC0+1×nC1+…n×nCnの値の求め方 0×nC0+1×nC1+…n×nCnは R×nCr=n×(n-1)C(r-1)より 0×nC0+1×nC1+…n×nCn =1×nC1+…n×nCn =n(n-1C0+n-1C1+…+n-1Cn-1) =n×2^n ですね。 二項定理とフェルマーの定理との関連 たぶんこの場合の「フェルマーの定理」とは 「pを素数、kをpで割り切れない自然数とするとき、 k^(p-1)-1はpで割り切れる。」…※ という定理のことでしょうか。 二項定理をつかえば、 「pを素数、kを自然数とするとき、k^p-kはpで割り切れる。」…* ことが数学的帰納法で示せます。 証明 k=1のとき 1^p-1=1-1=0はpで割り切れるので「*」は正しい k=hのとき 「*」は正しい、つまりh^p-hは素数pで割り切れると仮定する。 (h+1)^p-(h+1) =h^p-h+pC(p-1)×h^(p-1)+pC(p-2)×h^(p-2)+…+(pC1)×h 1≦r≦p-1なる任意のrに対して pCr={p×(p-1)×…×(p-r+1)}/(1×2×…×r) 分子がpで割り切れる、かつ分母がpと互いに素なので pCrはpで割り切れます。 よって、 pC(p-1)×h^(p-1)+pC(p-2)×h^(p-2)+…+(pC1)×hはpで割り切れます。 また帰納法の仮定よりh^p-hはpで割り切れます。 よって、 (h+1)^p-(h+1) =h^p-h+pC(p-1)×h^(p-1)+pC(p-2)×h^(p-2)+…+(pC1)×h もpで割り切れます。 k=h+1のときも「*」は正しい。 よって数学的帰納法により「*」は正しい。 「*」が正しければ、「※」が正しいことの証明 「*」よりk^p-k=k×{k^(p-1)-1}はpで割り切れる。 kとpは互いに素だから、k^(p-1)-1はpで割り切れる。 よって「※」が正しいことが示された。