周期性

数学オリンピック予選問題（2000年1月10日）
[40C20(Cはコンビネーションを表す)を41 で割った余りを求めよ]
というシンプルな問題.
今朝解いて面白かったので掲載.
手に負えなそうな数が出てきた場合は身近なところから計算してみると
答えにたどりつきやすいかも？
40C0 = 1 は41で割ると1
40C1 = 40は41で割ると40
40C2 = 780は41で割ると1
40C3 = 9880は41で割ると40
この辺で不思議な周期性に気づくと解答に近づく(と個人的に思います)
コンビネーションの性質
nCm = (n-1)Cm + (n-1)C(m-1)を思い出すと,
41C1 = 40C0+40C1
41C2 = 40C1+40C2
…
41C20 = 40C19+40C20

ところで41Cn(nは1以上40以下)は41で割りきれるので
この周期が出てくる.つまり40C0 = 1　mod 41なので
40Cnを41で割った数の列は隣同士足した数が41で割り切れなければなりません.
この数列は初項が1なのでこの数列は
{1,40,1,40,1,40,…}という形になり,
従って答えは1となります.

注：41Cnが41で割り切れるというものは一般のp(素数)に対して
示すことができます.
rを1≦r≦p-1となる自然数とすると
r * pCr = p * (p-1)C(r-1)
より右辺がpで割りきれ,rはpで割り切れないために
pCrはpで割り切れなければならない.
つまり,この性質により,
一般の素数pに対して(p-1)Cr mod p が分かります.

注:n mod mとは,nをmで割った時の余りを表します.