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