【整数の旅２】
こんにちは、数学好きの独り言です。
整数シリーズの第二回は前回の内容と関連のある問題を扱っていきます。
前回の問題は二項係数に関する問題でした。基本的に二項係数は難易度が高いことが多いので、しっかりと演習を積んでから問題に臨んだ方がよいです。ただ出る可能性は高くないのでなかなか難しいところですね。
しかし、東大は幾年かに一度二項係数に関する問題を出しています。東大を受験する人はしっかりと過去問を演習して対策しておきましょう。
ということで今回は東大数学の中でも難問と呼ばれる2021第四問を扱いたいと思います。
（誘導を抜いて（４）のみ扱います。）
（問題）
2021C37 を４で割った余りを求めよ。
本来は誘導にのって答えますが、ここではこの問題を直接解きたいと思います。
では解いていきましょう。
まずぱっと見ですが手が動かないですね。実験も何も数が大きすぎてできないと思います。想像すらつかないでしょう。かといって気合で計算するわけにもいかないし…。まあ最悪４択か＾＾と考えた人もいるかもしれません。解答の道筋を書かないと意味ないですが。ということでさっそく詰まってしまいますが、前回と同じように二項定理の係数として見てあげましょう。以下法を４とします。
2021C37は ( 1 + x )^2021 の x^37の係数ですね。これを合同式を用いながら変形していきます。ここで使うのが次の式です。
( 1 + x )^4 ≡ 1 + 2x^2 + x^4 ≡ ( 1 + x^2 )^2
4C1 と 4C3 は４の倍数なので合同式では消えますね。4C2 は６になるので合同式で２になります。よって上式にようになるわけです。これを使ってどんどん指数を減らしていきましょう。注意としては指数が４の倍数の時にしか使えないので、４の倍数になるように工夫しながら変形していきます。
さて、因数が５個のところまで指数を減らしていくと ( 1 + x^64 )^30 が出るところまで行くと思います。ここで求めるものを考えると、この項は無視していいことに気付きたいです。なぜなら、この項を式変形していっても x^37 の係数に関係のある項はもう出てこないからです。（37より次数が高いものしかでてこない）よって前の４つの因数だけを考えればいいことになります。
考えるべきは x^37 の係数です。この係数がどのような時に作り出せるか考えましょう。感覚的にはたくさんあるような気がしますが、なんと x^32 , x^4 , x を選んだ時にしか現れないことが簡単に分かります。あとはウイニングランです。このようなパターンは2通りあるので漏らさずに数えると、①では係数が２，②では係数が１となります。よってこの二つを足すと３になり、これが mod 4 で式変形した 2021C37 の係数なので答えは３となります。
（解説終わり）
いかがでしょうか。二項定理を使うことですんなり解くことができました。これを使えば 2021C37 以外でも４で割った余りを考えることができます。（例えば 2021C35 を４で割った余りは x^35 の係数なので２になる。）もちろん４で割った余り以外での役に立ちます。どんな問題に対しても有効な手段となり得るのでぜひ使いこなせるようにしたいですね。
次回は世界的にも有名である難問を解いていきます。mod と因数分解が大活躍します。それでは！