自然数$a,\ b$に対して，$a = bq+r,\ 0 \leqq r \leqq b-1$を満たす整数$q,\ r$がただ1組存在する．このとき$q$は$a$を$b$で割った商，$r$は$a$を$b$で割った余りという．自然数$a_0,\ a_1$が与えられたとき，数列$\{a_n\},\ \{q_n\}$は次の性質を満たすものとする．
[(i)] $q_n$は$a_{n-1}$を$a_n$で割った商 [(ii)] $\biggl( \begin{array}{c} a_n \\ a_{n+1} \end{array} \biggr)=\biggl( \begin{array}{cc} 0 & 1 \\ 1 & -q_n \end{array} \biggr) \biggl( \begin{array}{c} a_{n-1} \\ a_{n} \end{array} \biggr)$
ただし，$a_{N+1}=0$となる自然数$N$が存在すれば，$n>N$に対して$q_n$および$a_{n+1}$は定義しない．このとき，次の問いに答えよ．
(1) $a_{N+1}=0$となる自然数$N$が存在することを証明せよ．
(2) $a_N=aa_0+ba_1$を満たす整数$a,\ b$が存在することを証明せよ．
(3) $a_N$は$a_0$と$a_1$の最大公約数であることを証明せよ．