$a_{1}$, $a_{2}$, $\ldots$, $a_{n}$ を整数とし, \begin{align*} d_{2} &= \gcd(a_{1},\,a_{2}),\quad d_{n}=\gcd(d_{n-1},\,a_{n})\quad (n=3, 4, \ldots), \\ d'_{n} &= \gcd(a_{1},\,a_{2},\,\ldots,\,a_{n})\quad (n=2, 3, \ldots) \end{align*} とおく. このとき, $$ d_{n} = d'_{n}\quad (n=2, 3, \ldots) $$ が成り立つことを証明せよ.
解答例 1
$n$ に関する数学的帰納法によって証明する.
$n=2$ のとき, $d_{2}=d'_{2}=\gcd(a_{1},\,a_{2})$ であるから, 問題の主張は正しい.
$n=k$ のとき, 問題の主張が正しいと仮定すると, \begin{equation} d_{k+1}=\gcd(d_{k},\,a_{k+1}) = \gcd(d'_{k},\,a_{k+1}). \tag{1} \end{equation} $d'_{k+1}$ は $a_{1}$, $a_{2}$, $\ldots$, $a_{k}$ を割り切るから, $d'_{k}$ を割り切る. さらに, $d'_{k+1}\mid a_{k+1}$ より, $d'_{k+1}\mid d_{k+1}$. 逆に, (1) より $d_{k+1}\mid d'_{k}$ であるから, $d_{k+1}$ は $a_{1}$, $a_{2}$, $\ldots$, $a_{k}$ を割り切る. さらに, $d_{k+1}\mid a_{k+1}$ より, $d_{k+1}\mid d'_{k+1}$. ゆえに, $d'_{k+1}\mid d_{k+1}$ かつ $d_{k+1}\mid d'_{k+1}$ であるから, $d_{k+1}=d'_{k+1}$. したがって, $n=k+1$ のときも問題の主張は正しい.
以上より, すべての $n$ に関して, 問題の主張は正しい.
最終更新日：2011年11月02日