読者です 読者をやめる 読者になる 読者になる

ニ☆ウ☆ト☆ラ☆ボ

タイトルテスト中

不定方程式の整数解と最大公約数と: 足し算と掛け算のパズル(後編)

前回, 次のような計算 \begin{align} &0 \, \quad \, 1 \, \begin{array}{c} \stackrel{2}{\frown} \\[1.5em] {} \end{array} \, 2 \, \begin{array}{c} \stackrel{3}{\frown} \\[1.5em] {} \end{array} \, 7 \, \begin{array}{c} \stackrel{1}{\frown} \\[1.5em] {} \end{array} \, 9 \, \begin{array}{c} \stackrel{2}{\frown} \\[1.5em] {} \end{array} \, 25 \, \begin{array}{c} \stackrel{1}{\frown} \\[1.5em] {} \end{array} \, 34, \\[1.5em] &0 \, \quad \, 1 \, \begin{array}{c} \stackrel{1}{\frown} \\[1.5em] {} \end{array} \, 1 \, \begin{array}{c} \stackrel{2}{\frown} \\[1.5em] {} \end{array} \, 3 \, \begin{array}{c} \stackrel{1}{\frown} \\[1.5em] {} \end{array} \, 4 \, \begin{array}{c} \stackrel{3}{\frown} \\[1.5em] {} \end{array} \, 15 \, \begin{array}{c} \stackrel{2}{\frown} \\[1.5em] {} \end{array} \, 34 \end{align} をして,
何で同じ数が出てくるんだろう?
と思ったのでした. 今回は, これが成り立つ理由を述べます. まずは, 問題を定式化します.

数列 \[ \bigl( a_1, \, a_2, \, \ldots, \, a_n \bigr) \] に対して, 上の操作を行ったときに出てくる数を \[ \bigl[ a_1, \, a_2, \, \ldots, \, a_n \bigr] \] と書くことにします. すなわち, \[ 0 \, \quad \, 1 \, \begin{array}{c} \stackrel{a_1}{\frown} \\[1.5em] {} \end{array} \, A_1 \, \begin{array}{c} \stackrel{a_2}{\frown} \\[1.5em] {} \end{array} \, A_2 \, \begin{array}{c} \stackrel{a_3}{\frown} \\[1.5em] {} \end{array} \, \cdots \, \begin{array}{c} \stackrel{a_n}{\frown} \\[1.5em] {} \end{array} \, A_n =: \bigl[ a_1, \, a_2, \, \ldots, \, a_n \bigr]. \] 問題は次のように定式化されます: \[ \bigl[ a_1, \, a_2, \, \ldots, \, a_n \bigr] = \bigl[ a_n, \, a_{n-1}, \, \ldots, \, a_1 \bigr] \] は成り立つでしょうか?

2 つの証明を紹介します.

  1. 帰納法を用いるもの.
  2. 行列を用いるもの.

まず, 1 つ目. 帰納法で証明します. \( n = 1 \) のときは何も言うことがありません. \( n = 2 \) のときは, 定義より, \[ \bigl[ a_1, \, a_2 \bigr] = 1 + a_1 \, a_2. \] \( a_1 \) と \( a_2 \) を入れ換えても変化しません. \( n = 3 \) のときも定義より, \[ \bigl[ a_1, \, a_2, \, a_3 \bigr] = \bigl[ a_1 \bigr] + \bigl[ a_1, \, a_2 \bigr] a_3 = a_1 + \bigl(1 + a_1 \, a_2 \bigr) a_3. \] \( a_1 \) と \( a_3 \) を入れ換えても変化しません. \( n \ge 4 \) とします. 帰納法の仮定を用いて計算すると, \begin{align} \bigl[ a_1, \, &a_2, \, \ldots, \, a_n \bigr] = \bigl[ a_1, \, \ldots, \, a_{n-2} \bigr] + \bigl[ a_1, \, \ldots, \, a_{n-1} \bigr] a_n \\[1em] &= \bigl[ a_{n-2}, \, \ldots, \, a_1 \bigr] + \bigl[ a_{n-1}, \, \ldots, \, a_1 \bigr] a_n \\[1em] &= \Bigl( \bigl[ a_{n-2}, \, \ldots, \, a_3 \bigr] + \bigl[ a_{n-2}, \, \ldots, \, a_2 \bigr] a_1 \Bigr) \\[0.5em] &\qquad \qquad {} + \Bigl( \bigl[ a_{n-1}, \, \ldots, \, a_3 \bigr] + \bigl[ a_{n-1}, \, \ldots, \, a_2 \bigr] a_1 \Bigr) \, a_n \\[1em] &= \Bigl( \bigl[ a_{n-2}, \, \ldots, \, a_3 \bigr] + \bigl[ a_{n-1}, \, \ldots, \, a_3 \bigr] a_n \Bigr) \\[0.5em] &\qquad \qquad {} + \Bigl( \bigl[ a_{n-2}, \, \ldots, \, a_2 \bigr] + \bigl[ a_{n-1}, \, \ldots, \, a_2 \bigr] a_n \Bigr) \, a_1 \\[1em] &= \Bigl( \bigl[ a_3, \, \ldots, \, a_{n-2} \bigr] + \bigl[ a_3, \, \ldots, \, a_{n-1} \bigr] a_n \Bigr) \\[0.5em] &\qquad \qquad {} + \Bigl( \bigl[ a_2, \, \ldots, \, a_{n-2} \bigr] + \bigl[ a_2, \, \ldots, \, a_{n-1} \bigr] a_n \Bigr) \, a_1 \\[1em] &= \bigl[ a_3, \, \ldots, \, a_n \bigr] + \bigl[ a_2, \, \ldots, \, a_n \bigr] a_1 \\[1em] &= \bigl[ a_n, \, \ldots, \, a_3 \bigr] + \bigl[ a_n, \, \ldots, \, a_2 \bigr] a_1 \\[1em] &= \bigl[ a_n, \, \ldots, \, a_1 \bigr]. \end{align} 数列が反転しました. めでたしめでたし.

2 つ目. 簡単のために \begin{align} &A_{-1} = 0, \quad A_0 = 1, \\[1em] &A_k = \bigl[ a_1, \, \ldots, \, a_k \bigr] \quad 1 \le k \le n \end{align} と書きます. \( A_k \) の定義により, \[ A_k = A_{k-2} + A_{k-1} \, a_k , \quad 1 \le k \le n \] です. これを行列を使って書くと, \[ \begin{pmatrix} A_{k-1} \\ A_k \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & a_k \end{pmatrix} \begin{pmatrix} A_{k-2} \\ A_{k-1} \end{pmatrix}, \quad 1 \le k \le n \] となります. したがって, \[ \begin{pmatrix} A_{n-1} \\ A_n \end{pmatrix} = \begin{pmatrix} 0 & 1 \\ 1 & a_n \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & a_{n-1} \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & a_1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \] です. これより, \[ \bigl[ a_1, \, \ldots, \, a_n \bigr] = \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & a_n \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & a_{n-1} \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & a_1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix}. \] この式より, \[ \bigl[ a_n, \, \ldots, \, a_1 \bigr] = \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & a_1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & a_2 \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & a_n \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix} \] ですが, 転置をとると, \[ \bigl[ a_n, \, \ldots, \, a_1 \bigr] = \begin{pmatrix} 0 & 1 \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & a_n \end{pmatrix} \begin{pmatrix} 0 & 1 \\ 1 & a_{n-1} \end{pmatrix} \cdots \begin{pmatrix} 0 & 1 \\ 1 & a_1 \end{pmatrix} \begin{pmatrix} 0 \\ 1 \end{pmatrix}. \] めでたく, \[ \bigl[ a_1, \, \ldots, \, a_n \bigr] = \bigl[ a_n, \, \ldots, \, a_1 \bigr] \] が示されました. 計算しなくてよいところが, うれしい証明です.

広告を非表示にする