二項定理について

質問

(99)＾10の下位５桁の数を求める問題で
99=（１０＾2)*-1
とみて二項定理を用いると
(99＾10)={(10＾2)-1}＾10
=Σ(10,r=0) 10Cr*((-1)＾(10-r))*{(10)＾2}＾r
となり、計算がとても大変です。
他に簡単に求めれる方法がありましたら教えてください。

Σ(2,r=0) 10Cr*(-1)＾{10-r}*(10)＾2r (mod　10＾5)
という式がどうやって現れたのか分かりません。
教えてください。

回答No.3

noocyte · ベストアンサー

> Σ(10,r=0) を Σ(2,r=0) がなぜ同じなのかがよく分かりません。

#2 の最後の式を少し変えて，次の式を考えましょう．

Sn ＝ Σ(n,r=0) (r＋1) * 10^r

つまりSnは，#2 のＳの最初のｎ＋１項の和です．

S0 ＝ 1．
S1 ＝ 1 ＋ 20 ＝ 21．
S2 ＝ 1 ＋ 20 ＋ 300 ＝ 321．
S3 ＝ 1 ＋ 20 ＋ 300 ＋ 4000 ＝ 4321．
S4 ＝ 1 ＋ 20 ＋ 300 ＋ 4000 ＋ 50000 ＝ 54321．
S5 ＝ 1 ＋ 20 ＋ 300 ＋ 4000 ＋ 50000 ＋ 600000 ＝ 654321．
S6 ＝ 1 ＋ 20 ＋ 300 ＋ 4000 ＋ 50000 ＋ 600000 ＋ 7000000 ＝ 7654321．
S7 ＝ 1 ＋ 20 ＋ 300 ＋ 4000 ＋ 50000 ＋ 600000 ＋ 7000000 ＋ 80000000 ＝ 87654321．

ここで，これらの下位５桁だけを取り出します．つまり mod 100000 です．

S0 mod 100000 ＝ 1
S1 mod 100000 ＝ 21
S2 mod 100000 ＝ 321
S3 mod 100000 ＝ 4321
S4 mod 100000 ＝ 54321
S5 mod 100000 ＝ 54321
S6 mod 100000 ＝ 54321
S7 mod 100000 ＝ 54321

ｎをこれ以上いくら増やしても，Sn mod 10000 ＝ 54321
から変化しないことはわかりますよね？

つまり ｎ≧４ならば (Sn mod 100000) ＝ (S4 mod 100000) ＝ 54321

つまり
((Σ(n,r=0) (r＋1) * 10^r) mod 100000)
＝ ((Σ(4,r=0) (r＋1) * 10^r) mod 100000)．

元の課題も同様に考えてください．

> Σ(10,r=0) を Σ(2,r=0) がなぜ同じなのかがよく分かりません。

念のためにもう一度言っておきますが，mod 100000 をはずしたら同じにはなりませんよ．

お礼

丁寧な説明ありがとうございます。
やっと理解することが出来ました。
どうもありがとうございました

回答No.2

noocyte

> (mod　10＾5)はｘが100000で割り切れると考えるのでしょか？

(X mod 100000) は「X を100000で割った余り」という意味です．
だからＸの下位５桁．
(例：1234567890 mod 100000 ＝ 67890)

また，X≡Y (mod 10000) と書いた場合は，X を100000で割った余りと，
Y を100000で割った余りが等しいということです．
つまり X の下位５桁と Y の下位５桁が同じということ．
(例：1234567890≡9999967890 (mod 100000))

> Σ(10,r=0) 10Cr*((-1)＾(10-r))*{(10)＾2}＾r
> から
> Σ(2,r=0) 10Cr*((-1)＾(10-r))*{(10)＾2r}になるのが分かりません。

その２つの式が等しいわけではありません．

(Σ(10,r=0) 10Cr*((-1)＾(10-r))*{(10)＾2}＾r) mod 10^5
と
(Σ(2,r=0) 10Cr*((-1)＾(10-r))*{(10)＾2r}) mod 10^5

が等しいのです．だから #1 に書いたとおり，
Σ(10,r=0) を Σ(2,r=0) にしてもいいのです．

{(10) ^ 2} ^ r ＝ {(10) ^ 2r} なのはいいですよね？

以上の説明でわからなければ，二項係数はひとまずおいといて，
次の式の下位５桁を求める方法を考えてみてください．

S ＝ Σ(1000,r=0) (r＋1) * 10^r
　＝ 1 ＋ 20 ＋ 300 ＋ 4000 ＋ 50000 ＋ 600000 ＋ … ＋ (1001 * 10^1000)

律儀にＳを計算してから，その下位５桁を取りますか？
あたしゃヤですね．

補足

質問ばかりしてすいません。
Σ(10,r=0) を Σ(2,r=0) がなぜ同じなのかがよく分かりません。
例：1234567890≡9999967890 (mod 100000))
は分かりやすかったです。
modってよく分からなかったので参考になりました。

回答No.1

noocyte

> =Σ(10,r=0) 10Cr*((-1)＾(10-r))*{(10)＾2}＾r
> となり、計算がとても大変です。

ん？ 全然大変じゃないですよ．(笑)

各項に 100^r がかかっていて，題意より下位５桁を求めればいいので，
r≧3 の項は 1000000 の倍数となって下位５桁は全部０だから無視して OK．
だから r＝0，1，2 の項だけを計算すればいい．

> Σ(2,r=0) 10Cr*(-1)＾{10-r}*(10)＾2r (mod　10＾5)
> という式がどうやって現れたのか分かりません。

Σ(2,r=0) となる理由は上に書いたとおり．
(mod 10^5) は「下位５桁を求める」をそのまま式にしただけ．
ほかにわからないことありますか？

補足

Σ(10,r=0) 10Cr*((-1)＾(10-r))*{(10)＾2}＾r
から
Σ(2,r=0) 10Cr*((-1)＾(10-r))*{(10)＾2r}になるのが分かりません。

(mod　10＾5)はｘが100000で割り切れると考えるのでしょか？