トップ› 東京大学› 1993年› 理系第2問

東京大学 1993年理系第2問解説

方針・初手

倍数条件や余りに関する問題であるため、漸化式を適切な法に対する合同式として捉えることが基本である。（1）では法を 2、（2）では法を 10（あるいは互いに素な 2 と 5 に分ける）として、数列 $\{a_n\}$ の余りの周期性を調べる。

解法1

(1)

すべての整数に対して、法を 2 とした合同式を考える。与えられた漸化式 $a_{n+2} = 3a_{n+1} - 7a_n$ は、法 2 において $3 \equiv 1$、$ -7 \equiv 1$ であるから、次のように表せる。

$$ a_{n+2} \equiv a_{n+1} + a_n \pmod 2 $$

これと初期条件 $a_1 = 1 \equiv 1$、$a_2 = 3 \equiv 1$ を用いて、数列 $\{a_n\}$ の法 2 における値を順に調べると、以下のようになる。

$n=1$ のとき、$a_3 \equiv a_2 + a_1 \equiv 1 + 1 \equiv 0 \pmod 2$
$n=2$ のとき、$a_4 \equiv a_3 + a_2 \equiv 0 + 1 \equiv 1 \pmod 2$
$n=3$ のとき、$a_5 \equiv a_4 + a_3 \equiv 1 + 0 \equiv 1 \pmod 2$
$n=4$ のとき、$a_6 \equiv a_5 + a_4 \equiv 1 + 1 \equiv 0 \pmod 2$

連続する 2 項の組 $(a_n, a_{n+1})$ を mod 2 で考えると、 $(1, 1) \to (1, 0) \to (0, 1) \to (1, 1) \to \dots$ と遷移する。漸化式より次の項は直前の 2 項のみで一意に定まるため、数列 $\{a_n\}$ の法 2 における値は $(1, 1, 0)$ を 1 周期とする周期 3 の列となる。すなわち、任意の自然数 $k$ に対して以下が成り立つ。

$$ \begin{cases} a_{3k-2} \equiv 1 \pmod 2 \\ a_{3k-1} \equiv 1 \pmod 2 \\ a_{3k} \equiv 0 \pmod 2 \end{cases} $$

したがって、$a_n \equiv 0 \pmod 2$ となること、つまり $a_n$ が偶数となることと、$n$ が 3 の倍数となることは同値である。（証明終）

(2)

$a_n$ が 10 の倍数となるための条件は、$a_n$ が 2 の倍数かつ 5 の倍数となることである。

2 の倍数となる条件は（1）より $n$ が 3 の倍数となることである。

次に、5 の倍数となる条件を法 5 の合同式を用いて調べる。法 5 において $3 \equiv 3$、$-7 \equiv -2$ であるから、与えられた漸化式は次のように表せる。

$$ a_{n+2} \equiv 3a_{n+1} - 2a_n \pmod 5 $$

これと初期条件 $a_1 = 1 \equiv 1$、$a_2 = 3 \equiv 3$ を用いて、数列 $\{a_n\}$ の法 5 における値を順に調べる。

$n=1$ のとき、$a_3 \equiv 3 \cdot 3 - 2 \cdot 1 = 7 \equiv 2 \pmod 5$
$n=2$ のとき、$a_4 \equiv 3 \cdot 2 - 2 \cdot 3 = 0 \pmod 5$
$n=3$ のとき、$a_5 \equiv 3 \cdot 0 - 2 \cdot 2 = -4 \equiv 1 \pmod 5$
$n=4$ のとき、$a_6 \equiv 3 \cdot 1 - 2 \cdot 0 = 3 \pmod 5$

$(a_5, a_6) \equiv (1, 3) \pmod 5$ となり、$(a_1, a_2) \equiv (1, 3) \pmod 5$ と一致した。前項 2 つの値が決まれば次の項の値は一意に定まるため、数列 $\{a_n\}$ の法 5 における値は $(1, 3, 2, 0)$ を 1 周期とする周期 4 の列となる。すなわち、任意の自然数 $m$ に対して以下が成り立つ。

$$ \begin{cases} a_{4m-3} \equiv 1 \pmod 5 \\ a_{4m-2} \equiv 3 \pmod 5 \\ a_{4m-1} \equiv 2 \pmod 5 \\ a_{4m} \equiv 0 \pmod 5 \end{cases} $$

したがって、$a_n \equiv 0 \pmod 5$ となること、つまり $a_n$ が 5 の倍数となるための条件は、$n$ が 4 の倍数となることである。

以上より、$a_n$ が 10 の倍数となることと同値な条件は、「$n$ が 3 の倍数」かつ「$n$ が 4 の倍数」である。3 と 4 は互いに素であるため、この条件は「$n$ が 12 の倍数」と同値である。