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

(1)

示すべき2つの式は，次の合同式と同値である。 $$a_n\equiv np+{\displaystyle \frac{n(n-1)}{2}}{p}^2(\mathrm{m}\mathrm{o}\mathrm{d}{p}^3),$$ $$b_n\equiv 1+np+n(n-1)p^2(\mathrm{m}\mathrm{o}\mathrm{d}{p}^3)\mathrm{.}$$ これを同時に数学的帰納法で示す。 $n=1$ のとき，$$a_1=p=1\cdot p+{\displaystyle \frac{1\cdot 0}{2}}{p}^2,$$ $$b_1=p+1=1+1\cdot p+1\cdot 0\cdot p^2$$ であるから成り立つ。

ある $n$ で成り立つと仮定する。まず$$\begin{array}{rl}{\displaystyle a_{n+1}}& {\displaystyle =a_n+p{b}_n}\\ {\displaystyle }& {\displaystyle \equiv (np+{\displaystyle \frac{n(n-1)}{2}}{p}^2)+p(1+np+n(n-1)p^2)(\mathrm{m}\mathrm{o}\mathrm{d}{p}^3)}\\ {\displaystyle }& {\displaystyle \equiv np+{\displaystyle \frac{n(n-1)}{2}}{p}^2+p+n{p}^2(\mathrm{m}\mathrm{o}\mathrm{d}{p}^3)}\\ {\displaystyle }& {\displaystyle =(n+1)p+{\displaystyle \frac{n(n+1)}{2}}{p}^2(\mathrm{m}\mathrm{o}\mathrm{d}{p}^3)\mathrm{.}}\end{array}$$ここで $p\cdot n(n-1)p^2$ は $p^3$ の倍数なので落とした。

次に$$\begin{array}{rl}{\displaystyle b_{n+1}}& {\displaystyle =p{a}_n+(p+1)b_n}\\ {\displaystyle }& {\displaystyle \equiv p(np+{\displaystyle \frac{n(n-1)}{2}}{p}^2)+(p+1)(1+np+n(n-1)p^2)(\mathrm{m}\mathrm{o}\mathrm{d}{p}^3)}\\ {\displaystyle }& {\displaystyle \equiv n{p}^2+\{1+np+n(n-1)p^2\}+\{p+n{p}^2\}(\mathrm{m}\mathrm{o}\mathrm{d}{p}^3)}\\ {\displaystyle }& {\displaystyle =1+(n+1)p+n(n+1)p^2(\mathrm{m}\mathrm{o}\mathrm{d}{p}^3)\mathrm{.}}\end{array}$$したがって $n+1$ でも2つの合同式が成り立つ。数学的帰納法により，すべての自然数 $n$ で成り立つ。

よって $a_n-{\displaystyle \frac{n(n-1)}{2}}{p}^2-np$ および $b_n-n(n-1)p^2-np-1$ はともに $p^3$ で割り切れる。

(2)

(1) の $a_n$ に関する合同式で $n=p$ とおくと，$$\begin{array}{rl}{\displaystyle a_p}& {\displaystyle \equiv p\cdot p+{\displaystyle \frac{p(p-1)}{2}}{p}^2(\mathrm{m}\mathrm{o}\mathrm{d}{p}^3)}\\ {\displaystyle }& {\displaystyle =p^2+{\displaystyle \frac{p-1}{2}}{p}^3(\mathrm{m}\mathrm{o}\mathrm{d}{p}^3)\mathrm{.}}\end{array}$$ $p$ は奇数であるから $(p-1)\mathrm{/}2$ は整数である。したがって，ある整数 $M$ を用いて $a_p=p^2+p^{3}M$ と書ける。

この式から $a_p=p^2(1+pM)$ であるため，$a_p$ は $p^2$ で割り切れる。一方，$1+pM$ は $p$ で割ると $1$ 余るので $p$ では割り切れない。したがって $a_p$ は $p^3$ では割り切れない。

2つの数列を縦ベクトルにまとめる。漸化式の係数行列を $I+pC$ と書けば、法 $p^3$ では二項展開の第2次まで残せばよい。各成分を読み取って(1)を一度に示し、(2)は $n=p$ を代入する。

(1) $${\mathit{v}}_n=\left(\begin{array}{c}{a}_n\\ b_n\end{array}\right),C=\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)$$とおく。漸化式と初期条件は$${\mathit{v}}_{n+1}=(I+pC){\mathit{v}}_n,{\mathit{v}}_1=pC{\mathit{e}}_2+{\mathit{e}}_2=(I+pC){\mathit{e}}_2$$と書ける。ただし $${\mathit{e}}_2=(0,1{)}^{\mathsf{T}}$$ である。したがって$${\mathit{v}}_n=(I+pC{)}^n{\mathit{e}}_2\mathrm{.}$$法 $p^3$ では $p^3$ 以上を含む項を除けるから、二項展開より$${\mathit{v}}_n\equiv \{I+npC+{\displaystyle \frac{n(n-1)}{2}}{p}^2{C}^2\}{\mathit{e}}_2(\mathrm{m}\mathrm{o}\mathrm{d}{p}^3)\mathrm{.}$$ここで$$C{\mathit{e}}_2=\left(\begin{array}{c}1\\ 1\end{array}\right),C^2{\mathit{e}}_2=\left(\begin{array}{c}1\\ 2\end{array}\right)$$だから$$a_n\equiv np+{\displaystyle \frac{n(n-1)}{2}}{p}^2,b_n\equiv 1+np+n(n-1)p^2(\mathrm{m}\mathrm{o}\mathrm{d}{p}^3)\mathrm{.}$$よって問題文の2つの差はともに $p^3$ で割り切れる。

(2)
(1)の第1式へ $n=p$ を代入すると$$a_p\equiv p^2+{\displaystyle \frac{p-1}{2}}{p}^3\equiv p^2(\mathrm{m}\mathrm{o}\mathrm{d}{p}^3)\mathrm{.}$$$p$ は奇数なので $(p-1)\mathrm{/}2$ は整数である。ゆえに $a_p=p^2(1+pM)$ と書け、$1+pM$ は $p$ で割り切れない。したがって $a_p$ は $p^2$ で割り切れるが $p^3$ では割り切れない。