数列漸化式と最大公約数(神戸大2016理系第4問)
約数，公約数，最大公約数を次のように定める。
・2 つの整数 $a,b$ に対して，$a=bk$ をみたす整数 $k$ が存在するとき，$b$ は $a$ の約数であるという。
・2 つの整数に共通の約数をそれらの公約数という。
・少なくとも一方が 0 でない 2 つの整数の公約数の中で最大のものをそれれあの最大公約数という。
以下の問に答えよ。
(1) $a,b,c,p$ は 0 でない整数で $a=pb+c$ をみたしているとする。
(i) $a=18,b=30,c=-42,p=2$ のとき，$a$ と $b$ の公約数の集合 $S$，および $b$ と $c$ の公約数の集合 $T$ を求めよ。
(ii) $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)$，$a_1=3,a_2=4$
で定める。
(i) $a_{n+1}$ と $a_n$ の最大公約数を求めよ。
(ii) $a_{n+1}$ を $a_{n+2}$ と $a_n$ を用いて表わせ。
(iii) $a_{n+2}$ と $a_n$ の最大公約数を求めよ。
集合を求める
(1)から始めます。
ここでは $c=-42$ となっているように，約数は正の数だけではないことに注意しましょう。
18 と 30 の公約数の集合は
$S=\{1,2,3,6,-1,-2,-3,-6\}$ （答え）
同様に 30 と $-42$ の公約数の集合は
$T=\{1,2,3,6,-1,-2,-3,-6\}$ （答え）
倍数を考える
(ii)に進みます。
$a=pb+c$ を変形して
$c=a-pb$
$a$ と $b$ の最大公約数を $M$ とすると $a,b$ はともに $M$ の倍数です。そこで，$a=Ma’$，$b=Mb’$ とすると
$c=Ma’-p\cdot Mb’$
$=M(a’-pb’)$
よって，$c$ は $M$ の倍数であり，言い換えると $M$ は $c$ の約数ということです。
そして，$b$ と $c$ の最大公約数が $N$ であるということは，$N$ も $c$ の約数の一つであり，$M$ は $N$ よりも小さいか，または等しくなります。
つまり，$M\leqq N$ が成り立つ。
同様に
$a=pNb”+Nc”=N(pb”+c”)$
とすると，$N$ は $a$ の約数だから
$N\leqq M$
が成り立つ。
したがって，$N=M$ （証明終わり）
最大公約数を求める
(2)に進みます。
$a_{n+2}=6a_{n+1}+a_n$ $(n=1,2,\cdots)$
これを，(1)で用いた
$a=pb+c$
と比べてみましょう。$a_{n+2}=a$，$b=a_{n+1}$，$a_n=c$ とすると
$a_{n+2}$ と $a_{n+1}$ の最大公約数は $a_{n+1}$ と $a_n$ の最大公約数と等しい，ということが言えます。
つまり，これを進めていくと，$a_{n+1}$ と $a_n$ の最大公約数は $a_n$ と $a_{n-1}$ の最大公約数と等しい，$a_n$ と $a_{n-1}$ の最大公約数は $a_{n-1}$ と $a_{n-2}$ の最大公約数と等しい，・・・，$a_2$ と $a_1$ の最大公約数と等しい，となります。
したがって，$a_{n+1}$ と $a_n$ の最大公約数は 4 と 3 の最大公約数と等しいので
1 （答え）
式を変形する
(ii)に進みます。
$a_{n+2}=6a_{n+1}+a_n$ より
$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}$
また
$a_{n+2}=6a_{n+1}+a_n$ を移行して
$6a_{n+1}=a_{n+2}-a_n$
これを代入して
$a_{n+4}=37a_{n+2}+a_{n+2}-a_n$
$=38a_{n+2}-a_n$ （答え）
最大公約数を求める
(iii)に進みます。
$a_{n+4}=38a_{n+2}-a_n$ と $a=pb+c$ を比べると，$a_{n+4}$ と $a_{n+2}$ の最大公約数は $a_{n+2}$ と $a_n$ の最大公約数と等しい，となります。
あとは，(2)の(i)でやったことと同じなのですが，今度は $n$ を 2 つずつ減らしていくので，$n$ が奇数か偶数かで話が変わるはずです。
$n$ が奇数のとき，$a_{n+4}$ と $a_{n+2}$ の最大公約数は $a_3$ と $a_1$ の最大公約数と等しい。
$a_3=6a_2+a_1=27$ だから
$a_3$ と $a_1$ の最大公約数は 3
また，$n$ が偶数のとき，$a_{n+4}$ と $a_{n+2}$ の最大公約数は $a_4$ と $a_2$ の最大公約数と等しい。
$a_4=6a_3+a_2=166$ だから
$a_4$ と $a_2$ の最大公約数は 2
したがって
$n$ が奇数のとき 3
$n$ が偶数のとき 2 （答え）
SNSでシェア