2021年(令和3年)東京大学-数学(理科)[4] - [別館]球面倶楽部零八式markIISR

[4]

以下の問いに答えよ．

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

(2)正の整数 $a,b$ が $a\lt b$ を満たしているとする．このとき, $A={}_{4a+1}\mbox{C}_{4b+1},B={}_a\mbox{C}_b$ に対して $KA=LB$ となるような正の奇数 $K,L$ が存在することを示せ．

(3) $a,b$ は(2)の通りとし，さらに $a−b$ が $2$ で割り切れるとする． ${}_{4a+1}\mbox{C}_{4b+1}$ を $4$ で割ったあまりは ${}_a\mbox{C}_b$ を $4$ で割った余りと等しいことを示せ．

(4) ${}_{2017}\mbox{C}_{37}$ を $4$ で割った余りを求めよ．

Kummer の定理(2021.02.26)
Lucas の定理の拡張（Baileyの定理と呼ぶべきか）(2021.03.07)

2021.02.26記
(2) は Kummer の定理、二項係数は2で何回割れるか - 球面倶楽部零八式 mark II でうまくいくが，(3)をこの考え方でうまく説明できない、、、。4で割った余りが0、2の場合は2で2回以上割れる、1回しか割れないとなり(2)の考え方が使えるが，2で割れない場合、4で割った余りが1か3かを区別するような考え方ではないからである．最初は $a-b$ が偶数という条件を末尾で繰り上がりが起きないと考えれば良いかと思ったが，この方針は駄目なのか、、、。

[解答]

(1) $K=L+4N（Nは整数）$ とおけ，このとき
$KA-LB=L(A-B)+4NA=0$ と $L$ が奇数とから $A-B$ は4の倍数となり題意は示された．

(2) $a=b+n$ とおき， $A(n)={}_{4(b+n)+1}\mbox{C}_{4b+1}$ ， $B(n)={}_{b+n}\mbox{C}_{b}$ とおく．

(i) $n=1$ のとき， $A(1)=\dfrac{(4b+5)(4b+4)(4b+3)(4b+2)}{5\times 4\times 3\times 2}$ $=\dfrac{(4b+5)(b+1)(4b+3)(2b+1)}{5\times 3}$ ， $B(1)=b+1$ だから
$15A(1)=(4b+5)(4b+3)(2b+1)B(1)$
となり，奇数 $K(1)=15$ ， $L(1)=(4b+5)(4b+3)(2b+1)$ を用いて $K(1)A(1)=L(1)B(1)$ とかける．

(ii) $n=k$ のとき， $K(k)A(k)=L(k)B(k)$ とかける奇数 $K(k)$ ， $L(k)$ が存在すると仮定すると
$A(k+1)=\dfrac{(4b+4k+5)(4b+4k+4)(4b+4k+3)(4b+4k+2)}{(4b+5)(4b+4)(4b+3)(4b+2)}A(k)$ $=\dfrac{(4b+4k+5)(b+k+1)(4b+4k+3)(2b+2k+1)}{(4b+5)(b+1)(4b+3)(2b+1)}A(k)$ ， $B(k+1)=\dfrac{b+k+1}{b+1}B(k)$ だから
$A(k+1)=\dfrac{(4b+4k+5)(4b+4k+3)(2b+2k+1)}{(4b+5)(4b+3)(2b+1)}\dfrac{A(k)}{B(k)}B(k+1)$ $=\dfrac{(4b+4k+5)(4b+4k+3)(2b+2k+1)}{(4b+5)(4b+3)(2b+1)}\times\dfrac{L(k)}{K(k)}B(k+1)$
となり，
$(4b+5)(4b+3)(2b+1)K(k)A(k+1)$ $=(4b+4k+5)(4b+4k+3)(2b+2k+1)L(k)B(k+1)$
となるので，奇数 $K(k+1)=(4b+5)(4b+3)(2b+1)K(k)$ ， $L(k+1)=(4b+4k+5)(4b+4k+3)(2b+2k+1)L(k)$
を用いて $K(k+1)A(k+1)=L(k+1)B(k+1)$ とかける．

よって帰納的に題意は証明された．

(3) 以下 mod 4 で考える．(2) より
$K(2)=9\times 7\times 7 K(1)$ $\equiv 1\times (-1)\times (-1) \times (-1)$ $=-1$ ，
$L(2)=(4b+9)\times (4b+7)\times (2b+3) L(1)$ $\equiv 1\times (-1)\times (2b+3) \times \{1\times (-1)\times (2b+1)$ $=(2b+3)(2b+1)$ $=4b^2+4b+3)$ $\equiv -1$
となり， $K(2)-L(2)\equiv 0$ ．

$n=k$ のときに $K(k)-L(k)\equiv 0$ を仮定すると，
$K(k+2)=(4b+9)(4b+7)(2b+3)(4b+5)(4b+3)(2b+1)K(k)$ $=(4b+9)(4b+7)(4b+5)(4b+3)(4b^2+4b+3)K(k)$ ，
$L(k+2)=(4b+4k+9)(4b+4k+7)(2b+2k+3)(4b+4k+5)(4b+4k+3)(2b+2k+1)L(k)$ $=(4b+4k+9)(4b+4k+7)(4b+4k+5)(4b+4k+3)\{4(b+k)^2+4(b+k)+3\}L(k)$
だから，mod 4 で
$K(k+2)\equiv 9\times 7\times 5\times 3\times 3K(k)$ $\equiv -K(k)$ ，
$L(k+2)\equiv 9\times 7\times 5\times 3\times 3L(k)$ $\equiv -L(k)$ ，
が成立するので，
$K(k+2)-L(k+2)\equiv -\{K(k)-L(k)\} \equiv 0$
となり， $n=k+2$ でも成立．

よって，任意の正の偶数 $n$ について $K(n)-L(n)\equiv 0$ となり，(1)より任意の正の偶数 $n$ について $A(n)-B(n)\equiv 0$ が成立する．

(4) (2) より ${}_{2021}\mbox{C}_{37}$ $={}_{505}\mbox{C}_9$ $={}_{126}\mbox{C}_2$ $=63\times 125$ $\equiv 3\times 1$ $=3(\mbox{mod}\,4)$ だから答は $3$

大人の解答は(2)のみ．

[大人の解答]

(2) ${}_a\mbox{C}_b$ が2で割れる回数は2進法の足し算 $a=b+(a-b)$ における繰り上がりの回数であり，それは $4a=4b+4(a-b)$ における繰り上がりの回数に等しい（2進法の足し算の末尾の0を2個つけただけ）．そしてそれは $4a+1=4b+1+4(a-b)$ における繰り上がりの回数に等しい（1の位は $1+0=1$ で繰り上がらない）ので ${}_{4a+1}\mbox{C}_{4b+1}$ が2で割れる回数に等しい．よって
$\dfrac{A}{B}$ を既約分数で表現したものを $\dfrac{L}{K}$ とすれば，それは奇数÷奇数となって題意をみたす．

2021.03.07記
そういえば解答速報の後に twitter で、Lucas の定理と書いていた人がいたなぁ。

Lucas の定理は，

ラマヌジャンの遺した関数 (本格数学練習帳第1巻)

作者:D.フックス,S.タバチニコフ
岩波書店

Amazon

の p.39 定理2.1 にあり，その特殊な場合として

$p$ を素数とするとき ${}_{pa+1}\mbox{C}_{pb+1}$ $\equiv{}_{a}\mbox{C}_b$

が成り立つというものである．本問の場合， $4$ は素数ではないので，これをこのまま適用することができない．
Lucas の定理を素数の羃に拡張したものとして

D.F. Bailey, Two p^3 variations of Lucas’ theorem, J. Number Theory 35 (1990), 208–215.(pdf) Theorem 3 に Lucas の定理の拡張として

$p$ を素数， $N,R,n_0,r_0$ は非負， $n_0,r_0$ は $p$ より小さいとき，
${}_{Np^2+n_0}\mbox{C}_{Rp^2+r_0}$ $\equiv{}_{N}\mbox{C}_R\times {}_{n_0}\mbox{C}_{r_0}（\mbox{mod}\, p^2）$

があり， $p=2,m_0=n_0=1$ とすると
${}_{4n+1}\mbox{C}_{4m+1}$ $\equiv{}_{n}\mbox{C}_m（\mbox{mod}\, 4）$
と，本問の結果が得られる．これを拡張したものに関して Romeo Meštrović, Variations of Lucas' Theorem Modulo Prime Powers の Theorem A に K.S.Davis and W. A. Webb, A binomial coefficient congruence modulo prime powers, J. Number Theory. 43 (1993), 20–2 を引用した

$p$ を素数， $n,m,n_0,m_0$ は非負， $n_0,m_0$ は $p^s$ より小さいとき，
${}_{np^{k+s}+n_0}\mbox{C}_{mp^{k+s}+m_0}$ $\equiv{}_{np^k}\mbox{C}_{mp^k}\times {}_{n_0}\mbox{C}_{r_0}（\mbox{mod}\, p^{k+1}）$

という定理がある．この論文の p.7 に本問の証明があるが，
${}_{2n}\mbox{C}_{2m}$ $\equiv (-1)^m{}_{n}\mbox{C}_m-(-1)^m 2n^2{}_{n-1}\mbox{C}_{m-1}\times\dfrac{3+(-1)^m}{2}（\mbox{mod}\, 2^{2{\rm ord}_2(n)+2}）$
を利用していて大変そうだ．この式で， $n,m$ の偶奇で場合分けしていずれの場合も ${}_{2n}\mbox{C}_{2m}={}_{n}\mbox{C}_{m}（\mbox{mod}\,4）$ が成立することを示すのはちょっと面倒そうだ．

Romeo Meštrović, Lucas' theorem: its generalizations, extensions and applications (1878--2014) の方が新しくて良いかも。

まぁ、定理の証明はともかく、

Lucas の定理（上記書籍のp.41系2.2）は $p$ 進数表示の対応する桁の二項係数の積，つまり $n=(n_r\cdots n_0)_p$ ， $m=(m_r\cdots m_0)_p$ （桁数を揃えるために頭に0をつける）とすると
$\displaystyle {}_n\mbox{C}_m\equiv \prod_{i=0}^r {}_{n_i}\mbox{C}_{m_i}（\mbox{mod}\,p）$
が成立するとういことであったが，Bailey は $p^2$ 進数表示の対応する桁の二項係数の積，つまり $n=(n_r\cdots n_0)_{p^2}$ ， $m=(m_r\cdots m_0)_{p^2}$ （桁数を揃えるために頭に0をつける）とすると
$\displaystyle {}_n\mbox{C}_m\equiv \prod_{i=0}^r {}_{n_i}\mbox{C}_{m_i}（\mbox{mod}\,p^2）$
が成立することを示したという訳である．

2021.03.13記

[大人の解答]

(2) Kummer の定理により， ${}_a\mbox{C}_b$ が2で割れる回数は2進法の足し算 $a=b+(a-b)$ における繰り上がりの回数であり，それは $4a=4b+4(a-b)$ における繰り上がりの回数に等しい（2進法の足し算の末尾の0を2個つけただけ）．そしてそれは $4a+1=4b+1+4(a-b)$ における繰り上がりの回数に等しい（1の位は $1+0=1$ で繰り上がらない）ので ${}_{4a+1}\mbox{C}_{4b+1}$ が2で割れる回数に等しい．よって
$\dfrac{A}{B}$ を既約分数で表現したものを $\dfrac{L}{K}$ とすれば，それは奇数÷奇数となって題意をみたす．

(3) $a,b$ を素数2の2乗である4進法であらわしたものを $a_4,b_4$ とすると， $4a+1,4b+1$ を4進法で表したものは $a_41, b_41$ （ $a_4,b_4$ それぞれの末尾に $1$ をつけてできる4進数）となる．

よって Bailey の定理により
$\displaystyle {}_{4a+1}\mbox{C}_{4b+1} \equiv\displaystyle {}_{a}\mbox{C}_{b}\times \displaystyle {}_{1}\mbox{C}_{1}\equiv\displaystyle {}_{a}\mbox{C}_{b}（\mbox{mod}\, 4）$

2023.01.25記
文献の追加
LUCAS’ THEOREM MODULO [tex:p^2]

[1409.3820] Lucas' theorem: its generalizations, extensions and applications (1878--2014)