$a$ を整数, $b_{1}$, $b_{2}$, $\ldots$, $b_{n}$ を正の整数とする. このとき, \begin{align*} & a = q_{n}b_{1}b_{2}\cdots b_{n} + r_{n-1}b_{1}b_{2}\cdots b_{n-1}+ \cdots + r_{1}b_{1} + r_{0}, \\ & 0\leq r_{i} < b_{i+1}\quad (0\leq i\leq n-1) \end{align*} を満たす整数 $q_{n}$, $r_{0}$, $\ldots$, $r_{n-1}$ がただ1組だけ存在することを証明せよ.
解答例 1
$n$ に関する数学的帰納法により証明する.
$n=1$ のときは, 除法の原理そのものである.
$n=k$ のとき, 問題の主張が正しいと仮定すると, \begin{align} & a = q_{k}b_{1}b_{2}\cdots b_{k} + r_{k-1}b_{1}b_{2}\cdots b_{k-1}+ \cdots + r_{1}b_{1} + r_{0}, \tag{1} \\ & 0\leq r_{i} < b_{i+1}\quad (0\leq i\leq k-1) \notag \end{align} を満たす整数 $q_{k}$, $r_{0}$, $\ldots$, $r_{k-1}$ がただ1組だけ存在する. さらに, $$ q_{k} = q_{k+1}b_{k+1} + r_{k},\quad 0\leq r_{k}< b_{k+1} $$ を満たす整数 $q_{k+1}$, $r_{k}$ がただ1組だけ存在する. これを (1) に代入すれば $$ a = q_{k+1}b_{1}b_{2}\cdots b_{k+1} + r_{k}b_{1}b_{2}\cdots b_{k}+ \cdots + r_{1}b_{1} + r_{0} $$ が得られる. したがって, $n=k+1$ のときも問題の主張は正しい.
以上より, すべての $n$ に関して問題の主張は正しい.
最終更新日：2011年11月02日