トップ› 九州大学› 2006年› 理系第3問

九州大学 2006年理系第3問解説

方針・初手

(1) は、数列の各項を $3$ で割った余りだけに着目し、合同式を用いて規則性を調べるか、数学的帰納法を用いて証明します。 (2) は、「互いに素である」ことの証明の定石通り、背理法と数学的帰納法を組み合わせます。「ある項で共通の素因数 $p$ を持つ」と仮定し、それが直前の項も共通の素因数 $p$ を持つことに繋がることを示して矛盾を導きます。

解法1

(1) 与えられた漸化式に従って、最初の数項を計算する。

$$ a_1 = 1, \quad b_1 = 1 $$

$$ a_2 = 2 \cdot 1 \cdot 1 = 2 $$

$$ b_2 = 2 \cdot 1^2 + 1^2 = 3 $$

$$ a_3 = 2 \cdot 2 \cdot 3 = 12 $$

$$ b_3 = 2 \cdot 2^2 + 3^2 = 17 $$

これより、$n = 3$ のとき $a_3 = 12 \equiv 0 \pmod 3$、$b_3 = 17 \equiv 2 \not\equiv 0 \pmod 3$ となり、条件を満たす。

$n \geqq 3$ について、「$a_n \equiv 0 \pmod 3$ かつ $b_n \not\equiv 0 \pmod 3$」であることを数学的帰納法で示す。

[1] $n = 3$ のときは上記より成立。

[2] $n = k$ ($k \geqq 3$) のとき、成立すると仮定する。すなわち、

$$ a_k \equiv 0 \pmod 3, \quad b_k \not\equiv 0 \pmod 3 $$

とする。 $b_k \not\equiv 0 \pmod 3$ より、$b_k \equiv 1$ または $b_k \equiv 2 \pmod 3$ であり、いずれの場合も、

$$ b_k^2 \equiv 1 \pmod 3 $$

である。$n = k+1$ のとき、漸化式より、

$$ a_{k+1} = 2 a_k b_k \equiv 2 \cdot 0 \cdot b_k \equiv 0 \pmod 3 $$

$$ b_{k+1} = 2 a_k^2 + b_k^2 \equiv 2 \cdot 0^2 + 1 \equiv 1 \not\equiv 0 \pmod 3 $$

となり、$n = k+1$ のときも成立する。

[1], [2] より、$n \geqq 3$ のすべての自然数について、$a_n$ は $3$ で割り切れるが、$b_n$ は $3$ で割り切れない。

(2) まず、すべての自然数 $n$ について、$b_n$ が奇数であることを数学的帰納法で示す。

[1] $n = 1$ のとき、$b_1 = 1$ は奇数であり成立する。

[2] $n = k$ のとき、$b_k$ が奇数であると仮定する。漸化式より、

$$ b_{k+1} = 2 a_k^2 + b_k^2 $$

ここで、$2 a_k^2$ は偶数、$b_k^2$ は奇数の平方なので奇数である。よって、（偶数）＋（奇数）となるため、$b_{k+1}$ も奇数である。したがって、すべての自然数 $n$ について $b_n$ は奇数である。

次に、$n \geqq 2$ のとき、$a_n$ と $b_n$ が互いに素であることを数学的帰納法で示す。

[1] $n = 2$ のとき、$a_2 = 2$、$b_2 = 3$ であり、これらの最大公約数は $1$ であるから、互いに素であり成立する。

[2] $n = k$ ($k \geqq 2$) のとき、$a_k$ と $b_k$ が互いに素であると仮定する。 $n = k+1$ のとき、$a_{k+1}$ と $b_{k+1}$ が互いに素でないと仮定し、$2$ つの数が共通の素因数 $p$ を持つとする。 $b_{k+1}$ は奇数であるから、$p \geqq 3$ の素数である。

$$ a_{k+1} = 2 a_k b_k $$

であり、これが $p$ の倍数となる。$p$ は $3$ 以上の素数であるから、$a_k$ が $p$ の倍数であるか、または $b_k$ が $p$ の倍数である。

(i) $a_k$ が $p$ の倍数であるとき $b_{k+1} = 2 a_k^2 + b_k^2$ が $p$ の倍数であり、$2 a_k^2$ も $p$ の倍数であるため、$b_k^2$ も $p$ の倍数となる。 $p$ は素数であるから、$b_k$ は $p$ の倍数となる。これは $a_k$ と $b_k$ が互いに素であるという仮定に矛盾する。

(ii) $b_k$ が $p$ の倍数であるとき $b_{k+1} = 2 a_k^2 + b_k^2$ が $p$ の倍数であり、$b_k^2$ も $p$ の倍数であるため、$2 a_k^2$ も $p$ の倍数となる。 $p \geqq 3$ の素数であるから、$a_k^2$ が $p$ の倍数となり、$a_k$ も $p$ の倍数となる。これも $a_k$ と $b_k$ が互いに素であるという仮定に矛盾する。

いずれにせよ矛盾が生じるため、$a_{k+1}$ と $b_{k+1}$ は共通の素因数を持たず、互いに素である。したがって、$n = k+1$ のときも成立する。

[1], [2] より、$n \geqq 2$ のすべての自然数について、$a_n$ と $b_n$ は互いに素である。

解説

漸化式で定まる数列の整数の性質を証明する、典型かつ重要な問題です。 (1) は合同式を活用して余りの推移に着目することで、実際の値を計算し続けることなくシンプルに証明できます。剰余類を利用する定石の手法です。 (2) は「互いに素」を証明するにあたって、「背理法」を用いるのが強力です。最大公約数を文字でおき、それが $1$ より大きいと仮定して矛盾を導く流れは非常によく出題されます。本問では、$b_n$ が常に奇数であること（素因数 $2$ を持たないこと）を事前に示しておくのが、場合分けの論理を崩さないための鍵となります。