トップ› 東京大学› 2008年› 文系第4問

東京大学 2008年文系第4問解説

方針・初手

（1）は、すべての自然数 $n$ についての命題であるため、数学的帰納法を用いるのが自然である。証明すべき式がやや複雑なため、法を $p^3$ とする合同式を用いて計算すると見通しが良くなる。

（2）は、（1）の結果に $n = p$ を代入し、$a_p$ を $p^3$ の倍数の部分とそうでない部分に分けて評価する。その際、$p$ が奇数であるという条件が係数の整数性を保証するために効いてくる。

解法1

(1)

以下、法を $p^3$ とした合同式 $\pmod{p^3}$ を用いて記述する。示すべき命題は、すべての自然数 $n$ に対して、次の2つの合同式が成り立つことである。

$$ a_n \equiv \frac{n(n-1)}{2}p^2 + np \pmod{p^3} $$

$$ b_n \equiv n(n-1)p^2 + np + 1 \pmod{p^3} $$

これを数学的帰納法により証明する。

(i)

$n=1$ のとき

与えられた定義より $a_1 = p$、$b_1 = p+1$ である。一方で、右辺に $n=1$ を代入すると、

$$ \frac{1 \cdot 0}{2}p^2 + 1 \cdot p = p $$

$$ 1 \cdot 0 \cdot p^2 + 1 \cdot p + 1 = p + 1 $$

となり、ともに左辺と一致する。よって $n=1$ のとき命題は成り立つ。

(ii)

$n=k$ ($k$ は自然数) のとき、命題が成り立つと仮定する。

すなわち、次が成り立つと仮定する。

$$ a_k \equiv \frac{k(k-1)}{2}p^2 + kp \pmod{p^3} $$

$$ b_k \equiv k(k-1)p^2 + kp + 1 \pmod{p^3} $$

このとき、$n=k+1$ について考える。漸化式 $a_{k+1} = a_k + p b_k$ より、

$$ \begin{aligned} a_{k+1} &\equiv \frac{k(k-1)}{2}p^2 + kp + p \left\{ k(k-1)p^2 + kp + 1 \right\} \\ &= \frac{k(k-1)}{2}p^2 + kp + k(k-1)p^3 + kp^2 + p \\ &\equiv \frac{k(k-1)}{2}p^2 + kp^2 + (k+1)p \\ &= \left\{ \frac{k(k-1)}{2} + k \right\} p^2 + (k+1)p \\ &= \frac{k^2+k}{2}p^2 + (k+1)p \\ &= \frac{(k+1)k}{2}p^2 + (k+1)p \pmod{p^3} \end{aligned} $$

となり、$a_{k+1}$ についても成立する。

また、漸化式 $b_{k+1} = p a_k + (p+1) b_k = p a_k + p b_k + b_k$ より、

$$ p a_k \equiv p \left\{ \frac{k(k-1)}{2}p^2 + kp \right\} = \frac{k(k-1)}{2}p^3 + kp^2 \equiv kp^2 \pmod{p^3} $$

$$ p b_k \equiv p \left\{ k(k-1)p^2 + kp + 1 \right\} = k(k-1)p^3 + kp^2 + p \equiv kp^2 + p \pmod{p^3} $$

これらを用いると、

$$ \begin{aligned} b_{k+1} &\equiv kp^2 + (kp^2 + p) + \left\{ k(k-1)p^2 + kp + 1 \right\} \\ &= \left\{ k + k + k(k-1) \right\} p^2 + (k+1)p + 1 \\ &= (k^2+k)p^2 + (k+1)p + 1 \\ &= (k+1)k p^2 + (k+1)p + 1 \pmod{p^3} \end{aligned} $$

となり、$b_{k+1}$ についても成立する。

(i), (ii) より、すべての自然数 $n$ に対して命題は成り立つ。すなわち、$a_n - \frac{n(n-1)}{2}p^2 - np$ と $b_n - n(n-1)p^2 - np - 1$ はともに $p^3$ で割り切れる。

(2)

（1）の結果より、ある整数 $M$ を用いて、$a_n$ は次のように表せる。

$$ a_n = M p^3 + \frac{n(n-1)}{2}p^2 + np $$

$n=p$ を代入すると、

$$ \begin{aligned} a_p &= M p^3 + \frac{p(p-1)}{2}p^2 + p^2 \\ &= p^2 \left\{ M p + \frac{p(p-1)}{2} + 1 \right\} \end{aligned} $$

ここで、$p$ は奇数であるから、$p-1$ は偶数となり、$\frac{p-1}{2}$ は整数である。よって、

$$ \frac{p(p-1)}{2} = p \cdot \frac{p-1}{2} $$

は $p$ の倍数となる。これを用いると、$a_p$ は次のように変形できる。

$$ a_p = p^2 \left\{ p \left( M + \frac{p-1}{2} \right) + 1 \right\} $$

$M + \frac{p-1}{2}$ は整数であるから、中括弧の中身 $p \left( M + \frac{p-1}{2} \right) + 1$ は整数であり、したがって $a_p$ は $p^2$ で割り切れる。

さらに、中括弧の中身は $p$ で割ると $1$ 余る整数である。$p \geqq 3$ であるから、この数は $p$ の倍数ではない。したがって、$a_p$ を $p^2$ で割った商は $p$ で割り切れないため、$a_p$ は $p^3$ では割り切れない。

以上により題意は示された。

解説

連立漸化式と整数の性質を絡めた問題である。（1）のような複雑な式の倍数証明は、まともに等式で扱うと記述が煩雑になりやすい。合同式を導入し、法を $p^3$ として計算を進めることで、高次項（$p^3$ の倍数となる項）を早い段階で消去でき、計算ミスを防ぐことができる。

（2）は、（1）で得られた合同式ではなく、等式に戻して評価することが重要である。合同式 $\pmod{p^3}$ の世界では $a_p \equiv p^2 \pmod{p^3}$ となるが、これだけでは「$a_p$ が $p^2$ の倍数であること」は直ちに言えるものの、「$p^3$ の倍数ではないこと」の厳密な証明としてはやや言葉足らずになる恐れがある。整数の定数 $M$ を用いて立式し、$p^2$ でくくった残りの部分が $p$ の倍数でないことを明示する手順が確実である。また、「$p$ が奇数」という条件から $\frac{p-1}{2}$ が整数になることの言及を忘れないようにしたい。