問題#Ⅰ008 ★★☆☆
約数、公約数、最大公約数を次のように定める。
・$2$つの整数$a$、$b$に対して、$a=bk$ をみたす整数$k$が存在するとき、$b$は$a$の約数であるという。
・$2$つの整数に共通の約数をそれらの公約数という。
・少なくとも一方が$0$でない$2$つの整数の公約数の中で最大のものをそれらの最大公約数という。
以下の問に答えよ。
（１）$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$でない任意の整数とする。
（２）自然数の列$\{a_n\}$を$$a_{n+2}=6a_{n+1}+a_{n} \ (n=1,2,⋯)、a_1=3、a_2=4$$で定める。
(ⅰ) $a_{n+1}$と$a_n$の最大公約数を求めよ。
(ⅱ) $a_{n+4}$を$a_{n+2}$と$a_n$を用いて表せ。
(ⅲ) $a_{n+2}$と$a_n$の最大公約数を求めよ。
《ポイント》
数列の最大公約数に関する問題です。細かく誘導されているので順々に解きましょう。（１）のⅱではユークリッドの互除法で特有の証明法を用いるので、しっかり覚えておきたいところ。
《解答例》
（１）
（ⅰ）
$a=18$、$b=30$、$c=−42$、$p=2$ のとき、$a=2\cdot3^2$ と $b=2\cdot3\cdot5$ の公約数の集合$S$は$$S=\{\pm1,\,\pm2,\,\pm3,\,\pm6\}$$となり、$b=2\cdot3\cdot5$ と $c=-2\cdot3\cdot7$ の公約数の集合$T$は$$T=\{\pm1,\,\pm2,\,\pm3,\,\pm6\}$$となる。
（答）$\color{red}{S=T=\{\pm1,\,\pm2,\,\pm3,\,\pm6\}}$
（ⅱ）
$$(*)\ \ \ a=pb+c$$とする。
$a$、$b$は$M$の倍数なので、$(*)$式より、$c$も$M$の倍数となる。よって$M$は$b$と$c$の公約数となるから、$b$と$c$の最大公約数$N$以下である。故に$$M \leqq N$$を得る。
一方、$b$、$c$は$N$の倍数なので、$(*)$式より、$a$も$N$の倍数となる。よって$N$は$a$と$b$の公約数となるから、$a$と$b$の最大公約数$M$以下である。故に$$M \geqq N$$を得る。以上より、$$M=N$$が成り立つ。
□
（２）
（ⅰ）
（１）の結果より、$a=a_{n+2}$、$b=a_{n+1}$、$c=a_{n}$、$p=6$ とすれば、$a_{n+2}$と$a_{n+1}$の最大公約数と、$a_{n+1}$と$a_n$の最大公約数は等しい。帰納的に$a_{n+1}$と$a_n$の最大公約数は $a_{2}=4$ と $a_{1}=3$ の最大公約数に等しくなるので、求める$a_{n+1}$と$a_n$の最大公約数は$1$である。
（答）$\color{red}{1}$
（ⅱ）
$$\begin{align}a_{n+4}&=6a_{n+3}+a_{n+2} \\ &=6(6a_{n+2}+a_{n+1})+a_{n+2} \\ &=37a_{n+2}+6a_{n+1} \\ &=37a_{n+2}+(a_{n+2}-a_{n}) \\ &=38a_{n+2}-a_{n} \end{align}$$
（答）$\color{red}{a_{n+4}=38a_{n+2}-a_{n}}$
（ⅲ）
（１）の結果より、$a=a_{n+4}$、$b=a_{n+2}$、$c=-a_{n}$、$p=38$ とすれば、$a_{n+4}$と$a_{n+2}$の最大公約数と、$a_{n+2}$と$a_n$の最大公約数は等しい。
よって$n$が奇数のとき、帰納的に$a_{n+2}$と$a_n$の最大公約数は $a_{3}=27$ と $a_{1}=3$ の最大公約数に等しくなるので、求める$a_{n+2}$と$a_n$の最大公約数は$3$である。
また、$n$が偶数のとき、帰納的に$a_{n+2}$と$a_n$の最大公約数は $a_{4}=166$ と $a_{2}=4$ の最大公約数に等しくなるので、求める$a_{n+2}$と$a_n$の最大公約数は$2$である。
（答）$n$が奇数のとき$\color{red}{3}$、$n$が偶数のとき$\color{red}{2}$
《コメント》
（１）のⅱは「$M \leqq N$ かつ $M \geqq N$ ならば $M=N$」という論法です。最大公約数が一致することの証明でよく用いられる手法なので、これを機に覚えておきたいですね！
（２）では（１）で示した内容を利用します。ⅲでは$n$について場合分けが必要なことに注意しましょう。
（出典：神戸大学 2016年）