約数，公約数，最大公約数を次のように定める． \begin{itemize}
$2$つの整数$a,\ b$に対して，$a=bk$をみたす整数$k$が存在するとき，$b$は$a$の約数であるという．
$2$つの整数に共通の約数をそれらの公約数という．
少なくとも一方が$0$でない$2$つの整数の公約数の中で最大のものをそれらの最大公約数という． \end{itemize} 以下の問に答えよ．
(1) $a,\ b,\ c,\ p$は$0$でない整数で$a=pb+c$をみたしているとする．
(ⅰ) $a=18$，$b=30$，$c=-42$，$p=2$のとき，$a$と$b$の公約数の集合$S$，および$b$と$c$の公約数の集合$T$を求めよ．
(ⅱ) $a$と$b$の最大公約数を$M$，$b$と$c$の最大公約数を$N$とする．$M$と$N$は等しいことを示せ．ただし，$a,\ b,\ c,\ p$は$0$でない任意の整数とする．
(2) 自然数の列$\{a_n\}$を \[ a_{n+2}=6a_{n+1}+a_n \ \ (n=1,\ 2,\ \cdots),\quad a_1=3,\quad a_2=4 \] で定める．
(ⅰ) $a_{n+1}$と$a_n$の最大公約数を求めよ．
(ⅱ) $a_{n+4}$を$a_{n+2}$と$a_n$を用いて表せ．
(ⅲ) $a_{n+2}$と$a_n$の最大公約数を求めよ．