17915：40C20≡？ (mod 41)...^^

問題17915(友人問)

40C20を41で割った余りを求めよ。

解答

デジャヴー ？

・わたしの...

40C20=40*39*...*21/(20*19*...*2*1)=m

(41-1)(41-2)...(41-20)=(20*19*...*1)m

20!≡20!*m (mod 41)

20!は41で割り切れない...

so...

m=40C20≡1

^^

実際に...

40C20=137846528820

(137846528820-1)/41=3362110459 と割り切れますね ^^