・2項係数の計算                       GAI 氏

 2項係数をC(n,r)で表すとき、C(7654567,4567654)を29で割った余りを出そうと計算機に
頼ってみると、余りにも大きな値になるので結果が判明できませんでした。
(メモリー数やプログラムの改善では可能でしょうが)

 何とか計算機に頼らず、こんな大きな数を相手に手計算で求める方法はないものでしょう
か?


 らすかるさんからのコメントです。(平成29年3月29日付け)

 手計算で求める方法がわかりませんので、とりあえず簡単なプログラムを作って調べたと
ころ、
    C(7654567,4567654)≡28 (mod 29)

となるようですね。

# プログラムで7654567より大きな数は扱っていませんので、そういう意味では手計算でも可
 能ですが、同じことを手計算でやったら相当かかるでしょうね。


 GAI さんからのコメントです。(平成29年3月29日付け)

 このサイトの「2項係数の性質」の性質の中で

(29)’・・・・・・・・・・・・・
    ・・・・・・・・・・・・・
この結果の特別な場合として示すことができます。
(もちろん合同多項式を使ったり、組合せ論的な直接証明も可能と思います。)


と記されているではないか!(→ 詳細

 知りたい情報は正に(ハ)’(これをLucas 合同式というらしい。)

 7654567=17 + 21*29 + 24*29^2 + 23*29^3 + 10*29^4
 4567654= 9 +  6*29 +  8*29^2 + 13*29^3 +  6*29^4  (手計算で十分OK)

これより、 C(17,9)=24310≡8 (mod 29)、C(21,6)=54264≡5、C(24,8)=735471≡2
       C(23,13)=1144066≡16、C(10,6)=210≡7 (これも少々面倒だが手計算OK)

従って、 C(7654567,4567654)=8*5*2*16*7=8960≡28 (mod 29) で、らすかるさんから頂い
ていた値を手に入れることが可能となった。

#いやーインターネットは実に便利。いろいろな情報がたちどころに手に入れられる。しかも
 何時も使っているこのサイトに掲載されていた。コルムさんの投稿に厳しいコメントを述べ
 た真意はここにあります。ご自分で探し出してみることが何より面白いからです。



                         投稿一覧に戻る