Fussy's Diary

去年も同じタイトルで投稿してました。そのとき買おうと思ってたサーキュレータは結局まだ持ってません。除湿機も同じ。
朝の 9 時頃に仕事で屋外にいたんですけど、短時間だったのにもかかわらず、あまりの暑さに頭がクラクラしました。明日もこんな感じなんでしょうか。

「数学問題bot」から今回はこの問題を選んでみました。

-----

■ コンビネーション C[40,20] = 40_C_20 を 41 で割った余りを求めよ。 ( 00 数オリ予選 )

これを解くのに以下の道具を使います。

整数 a と b について、その差 ( a - b ) が整数 n で割り切れるとき、「a と b は n を法として合同である」といい、a ≡ b ( mod n ) と表す。これを「合同式」という。

例えば、5 ≡ 1 ( mod 4 ) であり、19 ≡ 7 ( mod 6 ) です。負数のときも成り立つと考えることができて、例えば 1 ≡ -3 ( mod 4 ) になります。

合同式では以下の式が成り立ちます。

a ≡ b ( mod n ) かつ c ≡ d ( mod n ) なら

a ± c ≡ b ± d ( mod n ) ... (1)

a・c ≡ b・d ( mod n ) ... (2)

また、k と n が互いに素なら、

k・a ≡ k・b ( mod n ) ならば a ≡ k ( mod n ) ... (3)

も成り立ちます。これらを証明するのはそれほど難しくないので、ぜひともチャレンジしみてください。

さて、問題に戻ると、コンビネーション C[40,20] (以下 C と略記します) は

C = 40・39・ ... ・22・21 / 20!

で求めることができます。分子の部分を A とすると、これは 20! で割り切ることができます (組み合わせが必ず整数になることの証明もおもしろいテーマになると思いますがここでは省略します)。A の個々の数値を見ると

40 ≡ -1 ( mod 41 )、39 ≡ -2 ( mod 41 )、 ... 21 ≡ -20 ( mod 41 )

なので、先ほどの公式 (2) から

A = 40・39・ ... ・22・21 ≡ (-1)・(-2)・ ... (-19)・(-20) = 20! ( mod 41 )

となります。A は C に 20! を掛けたものであり 20!・C と等しいので、

A = 20!・C ≡ 20! ( mod 41 )

です。41 は素数で 20! と共通な因数は存在せず、これらは互いに素なので

C ≡ 1 ( mod 41 )

となり、答えは 1 になります。

-----

合同式、知ってると便利です。自分は学生時代習ったことがなくて後で知りました。大学受験でも利用できる場面があると思います。