Evolton

東京大学 2021年度 前期日程 第2次学力試験理系数学 第4問

以下の問いに答えよ。

(1) 正の奇数K,Lと正の整数A,BがKA=LBを満たしているとする。
Kを4で割った余りがLを4で割った余りと等しいならば,
Aを4で割った余りはBを4で割った余りと等しいことを示せ。

(2) 正の整数a, bがa>bを満たしているとする。
このとき,A=4a+1C4b+1,B=aCbに対して
KA=LBとなるような正の奇数K,Lが存在することを示せ。

(3) a, bは(2)の通りとし,さらにa−bが2で割り切れるとする。
4a+1C4b+1を4で割った余りはaCbを4で割った余りと等しいことを示せ。

(4) 2021C37を4で割った余りを求めよ。

難易度7/ 10計算量6/ 10目安30分

整数、場合の数、論証・証明 合同式、約数・倍数、場合分け、計算整理

方針

(1) は奇数が4を法として逆元をもつことを使う。(2) は正整数 M に含まれる2の個数を ν(M) とし,ν((4m)!)=3m+ν(m!) を用いて2つの二項係数に含まれる2の個数が等しいことを示す。(3) は階乗から2をすべて除いた奇数部分を4を法として比較する。a−b が偶数なら符号因子が打ち消し合う。(4) は(3)を2回適用する。

解答

(1) 仮定よりKA=LB,K≡L(mod4)である。奇数 K は K2≡1(mod4) を満たすので,4を法として逆元をもつ。したがって合同式 KA≡LB(mod4) の両辺に K の逆元をかけ,K≡L(mod4) を用いればA≡B(mod4)を得る。

(2) 正整数 M を割り切る2の最大の累乗の指数を ν(M) と書く。(4m)! では,2の倍数から少なくとも 2m 個,4の倍数からさらに m 個の2が現れ,4の倍数に残る追加分は m! に含まれる2の個数と一致する。よってν((4m)!)=3m+ν(m!)である。また 4m+1 は奇数なので ν((4m+1)!)=ν((4m)!) である。

n=a−b とおき,A=4a+1C4b+1,B=aCbとする。上の関係からν(A)=ν((4a+1)!)−ν((4b+1)!)−ν((4n)!)={3a+ν(a!)}−{3b+ν(b!)}−{3n+ν(n!)}=ν(B)である。共通の値を e としA=2eA0,B=2eB0と書けば,A0,B0 は正の奇数である。そこでK=B0,L=A0とおけば,KA=LB が成り立つ。

(3) 正整数 m に対し,m! から2の因子をすべて除いた奇数部分を Om とする。1,2,…,4m を4個ずつに分けて奇数部分を比べる。

4j の奇数部分は j の奇数部分であり,4j−2 の奇数部分は 2j−1 である。また(4j−3)(4j−1)≡−1(mod4)である。さらに 1,3,5,…,2m−1 のうち4で割って3余るものは ⌊m/2⌋ 個なのでO4m≡O4m+1≡(−1)m+⌊m/2⌋Om(mod4)となる。ここでεm=(−1)m+⌊m/2⌋とおく。

二項係数から2の因子を除いた奇数部分を比較すると,(2)で得た A0,B0 についてA0≡εaεbεnB0(mod4)である。いま n=a−b は偶数である。a=b+n を用いると,εaεbεn の指数の偶奇は⌊a2⌋+⌊b2⌋+n2=2⌊b2⌋+nの偶奇に等しく,これは偶数である。したがってA0≡B0(mod4)となる。(2)で選んだ K=B0,L=A0 は4で割った余りが等しいので,(1)より4a+1C4b+1≡aCb(mod4)を得る。

(4) 2021=4⋅505+1,37=4⋅9+1で,505−9=496 は偶数であるから,(3)より2021C37≡505C9(mod4)である。さらに505=4⋅126+1,9=4⋅2+1で,126−2=124 も偶数なので505C9≡126C2(mod4)である。最後に126C2=126⋅1252=63⋅125≡3(mod4)より,求める余りは3である。

総評

難度7、計算量6。想定時間は30分程度。巨大な二項係数を計算するのではなく、2の因子と奇数部分に分離して4を法とする情報を保つ問題である。(2)の核は ν((4m)!)=3m+ν(m!) で、これにより2つの二項係数の2進指数が一致する。(3)では2を除いた階乗の奇数部分を4個ずつ整理し、a−b が偶数であることが符号を打ち消す箇所を明示する必要がある。誘導の役割をつなげて書けば、使用する道具は高校数学の整数・合同式の範囲に収まる。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る東大の整数の問題で問題集を作る

出典: 東京大学 2021年度 前期日程 第2次学力試験 数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。