トップ› 名古屋大学› 2004年› 理系第5問

名古屋大学 2004年理系第5問解説

方針・初手

隣接する2項 $x_{n+1}$ と $x_n$ が互いに素であることを示すため、数学的帰納法、あるいは「条件を満たさない最小の $n$」を仮定する背理法（最小値の原理）を用いるのが定石である。ユークリッドの互除法の原理より、2つの整数 $A, B$ と任意の整数 $k$ について $\gcd(A, B) = \gcd(A - kB, B)$ が成り立つ。この性質を用いて漸化式から項の次数を下げていくことが鍵となる。以下、整数 $A, B$ の最大公約数を $\gcd(A, B)$ と表す。

解法1

すべての正の整数 $n$ について $x_{n+1}$ と $x_n$ が互いに素であることを、数学的帰納法を用いて示す。その準備として、まず次の補題を示す。

【補題】すべての正の整数 $n$ について、$x_n$ と $b$ は互いに素である。

数学的帰納法を用いて証明する。 $n=1$ のとき、$x_1=1$ であり、1と任意の整数は互いに素であるから成り立つ。 $n=k$ ($k \geqq 1$) のとき、$x_k$ と $b$ が互いに素である、すなわち $\gcd(x_k, b) = 1$ と仮定する。 $k=1$ のときは、$x_2=1$ より $\gcd(x_2, b) = \gcd(1, b) = 1$ となり成り立つ。 $k \geqq 2$ のときは、漸化式より

$$ x_{k+1} = a x_k + b x_{k-1} $$

であるから、ユークリッドの互除法の性質を用いると

$$ \gcd(x_{k+1}, b) = \gcd(a x_k + b x_{k-1}, b) = \gcd(a x_k, b) $$

問題の条件より $a$ と $b$ は互いに素であり、帰納法の仮定より $x_k$ と $b$ も互いに素であるから、$a x_k$ と $b$ は互いに素である。よって $\gcd(x_{k+1}, b) = 1$ となり、$n=k+1$ のときも成り立つ。以上より、すべての正の整数 $n$ について $x_n$ と $b$ は互いに素である。

【本題の証明】

すべての正の整数 $n$ について $x_{n+1}$ と $x_n$ が互いに素であることを、数学的帰納法を用いて証明する。

I $n=1$ のとき

$x_2=1, x_1=1$ より $\gcd(x_2, x_1) = \gcd(1, 1) = 1$ となり成り立つ。

II $n=k$ ($k \geqq 1$) のとき成り立つ、すなわち $\gcd(x_{k+1}, x_k) = 1$ と仮定する。

$n=k+1$ のとき、

$$ \gcd(x_{k+2}, x_{k+1}) = \gcd(a x_{k+1} + b x_k, x_{k+1}) = \gcd(b x_k, x_{k+1}) $$

ここで、帰納法の仮定より $x_k$ と $x_{k+1}$ は互いに素である。また、先ほど示した【補題】より、$b$ と $x_{k+1}$ も互いに素である。したがって、$b x_k$ と $x_{k+1}$ は互いに素であるから、$\gcd(b x_k, x_{k+1}) = 1$ すなわち $\gcd(x_{k+2}, x_{k+1}) = 1$ となる。よって、$n=k+1$ のときも成り立つ。

I, II より、すべての正の整数 $n$ について $x_{n+1}$ と $x_n$ は互いに素であることが示された。

解法2

背理法を用いて示す。すべての正の整数 $n$ に対して $x_{n+1}$ と $x_n$ が互いに素であると仮定しない。すなわち、$x_{n+1}$ と $x_n$ が互いに素でないような正の整数 $n$ が存在すると仮定し、そのような $n$ のうち最小のものを $k$ とする。

$x_1 = 1, x_2 = 1$ より $x_2$ と $x_1$ は互いに素であるから、$k \neq 1$ である。 $x_3 = a x_2 + b x_1 = a + b$ であり、$x_3$ と $x_2$ の最大公約数は $\gcd(a+b, 1) = 1$ であるから、$k \neq 2$ である。よって $k \geqq 3$ である。

$k$ の定義より、$x_{k+1}$ と $x_k$ は $1$ より大きい公約数をもつため、公約数となる素数 $p$ が存在する。すなわち、$x_{k+1}$ と $x_k$ はともに $p$ の倍数である。漸化式 $x_{k+1} = a x_k + b x_{k-1}$ より、

$$ b x_{k-1} = x_{k+1} - a x_k $$

右辺は $p$ の倍数であるから、$b x_{k-1}$ も $p$ の倍数となる。 $p$ は素数であるから、$p$ は $b$ の約数であるか、$x_{k-1}$ の約数である。

(i) $p$ が $x_{k-1}$ の約数である場合

$x_k$ は $p$ の倍数であるから、$x_k$ と $x_{k-1}$ は公約数 $p$ をもつ。これは $x_k$ と $x_{k-1}$ が互いに素でないことを意味し、「$x_{n+1}$ と $x_n$ が互いに素でない最小の正の整数が $k$ である」という仮定に矛盾する。

(ii) $p$ が $b$ の約数である場合

$k \geqq 3$ であるから、漸化式より $x_k = a x_{k-1} + b x_{k-2}$ が成り立つ。これを変形すると

$$ a x_{k-1} = x_k - b x_{k-2} $$

$x_k$ は $p$ の倍数であり、仮定より $b$ も $p$ の倍数であるから、右辺は $p$ の倍数となる。よって $a x_{k-1}$ は $p$ の倍数である。 $p$ は素数であるから、$p$ は $a$ の約数であるか、$x_{k-1}$ の約数である。もし $p$ が $a$ の約数であれば、$p$ は $b$ の約数でもあるため、$a$ と $b$ が公約数 $p$ をもつことになり、$a$ と $b$ が互いに素であるという問題の条件に矛盾する。よって $p$ は $x_{k-1}$ の約数でなければならない。すると $x_k$ も $p$ の倍数であるため、$x_k$ と $x_{k-1}$ は公約数 $p$ をもつことになり、(i) と同様に $k$ の最小性に矛盾する。

(i), (ii) のいずれの場合も矛盾が生じる。したがって、背理法の仮定は誤りであり、すべての正の整数 $n$ について $x_{n+1}$ と $x_n$ は互いに素である。

解説

隣接2項間の互いに素を示す問題の典型として、ユークリッドの互除法の原理が活躍する。解法1のように素直に帰納法を用いる場合は、「$b$ と $x_n$ が互いに素」という事実が暗に必要となるため、これを自分で補題として設定し証明する構成力が問われる。一方、解法2のように最小値の原理（背理法）を用いると、素数 $p$ が割り切るという条件に帰着できるため、補題を事前に用意しなくても自然な論理の展開で解答を作りやすい。整数問題における背理法の強力さを実感できる良問である。