東京大学理系 2014年度第5問解説

🕒 2016/12/22 🔄 2023/05/01

問題編

問題

　r を $0$ 以上の整数とし、数列 $\{ a_n \}$ を次のように定める。\[ a_1=r, \quad a_2=r+1, \quad a_{n+2}=a_{n+1}(a_n+1) \quad (n=1,2,3,\cdots) \]また、素数 p を１つとり、 $a_n$ を p で割った余りを $b_n$ とする。ただし、 $0$ を p で割った余りは $0$ とする。

(1) 自然数 n に対し、 $b_{n+2}$ は $b_{n+1}(b_n+1)$ を p で割った余りと一致することを示せ。
(2) $r=2$, $p=17$ の場合に、 $10$ 以下のすべての自然数 n に対して、 $b_n$ を求めよ。
(3) ある２つの相異なる自然数 n, m に対して、\[ b_{n+1}=b_{m+1} \gt 0, \quad b_{n+2}=b_{m+2} \]が成り立ったとする。このとき、 $b_n=b_m$ が成り立つことを示せ。
(4) $a_2, a_3, a_4, \cdots$ に p で割り切れる数が現れないとする。このとき、 $a_1$ も p で割り切れないことを示せ。

考え方

見かけはごつい感じがしますが、整数問題にしては易しいです。

(1)は与えられた式をそのまま変形するか、差が p の倍数になることを示します。(2)は計算するだけです。(3)も、差が p の倍数になることを示します。

(4)は(3)を使うことは予想できますが、(3)の前提を満たすものをどうやって見つけるかが言いにくいです。余りの組を考え、数は無限個なのに種類は有限個であることに注目しましょう。

解答編

問題

　r を $0$ 以上の整数とし、数列 $\{ a_n \}$ を次のように定める。\[ a_1=r, \quad a_2=r+1, \quad a_{n+2}=a_{n+1}(a_n+1) \quad (n=1,2,3,\cdots) \]また、素数 p を１つとり、 $a_n$ を p で割った余りを $b_n$ とする。ただし、 $0$ を p で割った余りは $0$ とする。

(1) 自然数 n に対し、 $b_{n+2}$ は $b_{n+1}(b_n+1)$ を p で割った余りと一致することを示せ。

解答

(1) $a_n$ を p で割ったときの商を $q_n$ とする。このとき\[ b_n=a_n-pq_n \]が成り立つ。

\begin{eqnarray} & & b_{n+2}-b_{n+1}(b_n+1) \\ &=& (a_{n+2}-p q_{n+2})-(a_{n+1}-p q_{n+1}) \{(a_n-p q_n)+1\} \\ &=& \{a_{n+2}-a_{n+1}(a_n+1)\} -p q_{n+2} +a_{n+1}p q_n + p q_{n+1} (a_n-p q_n+1) \\ &=& p \{ -q_{n+2} +a_{n+1}q_n + q_{n+1} (a_n-p q_n+1) \} \\ \end{eqnarray}となり、最後の式の波かっこの中は整数なので、 $b_{n+2}-b_{n+1}(b_n+1)$ は p の倍数となる。 $b_{n+2}$ は $0$ 以上 p 未満の整数なので、 $b_{n+1}(b_n+1)$ を p で割った余りと等しい。

解説

「余りが等しい」は「差が倍数」と言い換えたほうが変形しやすいです。今は示したい式が分かりやすいので、 $a_{n+2}$ の式を変形して $b_{n+1}(b_n+1)$ をあぶりだす方法でも、そんなに難しくありません。

解答編つづき

問題

(2) $r=2$, $p=17$ の場合に、 $10$ 以下のすべての自然数 n に対して、 $b_n$ を求めよ。

解答

(2) $a_1=r=2$ なので、 $b_1=2$ 。
$a_2=r+1=3$ なので、 $b_2=3$ 。

以降は、(1)より $b_{n+1}(b_n+1)$ を $17$ で割った余りを考えればよい。
$b_2 (b_1+1) =9$ なので、 $b_3=9$ 。
$b_3 (b_2+1) =36$ なので、 $b_4=2$ 。
$b_4 (b_3+1) =20$ なので、 $b_5=3$ 。

これ以降は、3つ前と同じ値が出てくるので、 $b_6=9$, $b_7=2$, $b_8=3$, $b_9=9$, $b_{10}=2$ と求められる。

解説

書き出すだけです。「循環する」ということに気づかせるための問題です。

解答編つづき

問題

(3) ある２つの相異なる自然数 n, m に対して、\[ b_{n+1}=b_{m+1} \gt 0, \quad b_{n+2}=b_{m+2} \]が成り立ったとする。このとき、 $b_n=b_m$ が成り立つことを示せ。

解答

(3) $b_{n+2} -b_{m+2}$ は p の倍数なので、(1)より次の式も p の倍数である。
\begin{eqnarray} & & b_{n+1}(b_n +1) -b_{m+1}(b_m +1) \\ &=& b_{n+1}b_n +b_{n+1} -b_{m+1}b_m -b_{m+1} \\ \end{eqnarray}ここで、 $b_{n+1}=b_{m+1}$ なので、 \begin{eqnarray} & & b_{n+1}b_n +b_{n+1} -b_{m+1}b_m -b_{m+1} \\ &=& b_{n+1} (b_n -b_m) \\ \end{eqnarray}ここで、 $b_{n+1}$ は正であり、 p とは互いに素なので、 $b_n-b_m$ は p の倍数となる。 $b_n$, $b_m$ はともに $0$ 以上 p 未満の整数なので、 $b_n -b_m=0$ が成り立つ。よって $b_n=b_m$ となる。

解説

$+2$ 同士が等しく、 $+1$ 同士も等しいので、(1)を使えばすぐに示せそうです。 $b_n-b_m$ が p の倍数なので $0$ しかありえない、というふうに持っていきます。

解答編つづき

問題

(4) $a_2, a_3, a_4, \cdots$ に p で割り切れる数が現れないとする。このとき、 $a_1$ も p で割り切れないことを示せ。

解答

(4) n を正の整数とする。

$(b_{n+1},b_{n+2})$ の組を考える。すべての正の整数 n に対して $0\lt b_{n+1}\lt p$ なので、この組の種類は、高々 $(p-1)^2$ 通りとなる。よって、\[ (b_{n+m+1},b_{n+m+2}) = (b_{n+1},b_{n+2}) \]を満たす正の整数 n, m が存在する。(3)の結果を複数回使うと、\[ b_1 = b_{m+1} \]が成り立つ。条件からこれは正なので、 $a_1$ は p で割り切れない。