2017年東京大学数学理系第4問（文系第4問）を解こう（４）

前回の続きです。
問題はこちら

$p=2+\sqrt{5}$ とおき,自然数 $n=1,2,3,\cdots$ に対して
$\displaystyle a_n=p^n+\left(-\frac{1}{p}\right)^n$
と定める。
以下の問いに答えよ。ただし設問(1)は結論のみをかけばよい。

(1) $a_1,a_2$ の値を求めよ。

(2) $n\geqq2$ とする。積 $a_1a_n$ を, $a_{n+1}$ と $a_{n-1}$ を用いて表せ。

(3) $a_n$ は自然数であることを示せ。

(4) $a_{n+1}$ と $a_n$ の最大公約数を求めよ。（2017 東京大学理科第4問文科第4問）

思考過程

$a_{n+1}$ と $a_n$ との最大公約数を求めよとのこと。
(1)から(3)まででわかることは
$a_{n+1}$ と $a_n$ がともに自然数であるということだけです。
$a_{n+1}$ と $a_n$ が具体的な自然数としてわかったわけではありません。
具体的な数として与えられているのは
$a_n=p^n+q^n$ ( $\displaystyle q=-\frac{1}{p}$ としています)・・・①
ということです。
(1),(2)でやったように $p+q,pq$ を利用してnの式で表された $a_{n+1}$ と $a_n$ を求めてから最大公約数を調べることもできそうですがどうにも面倒くさそうです。

とりあえずn=1のときの $a_2$ と $a_1$ から何がわかるか調べてみましょう。

$a_1=4=2^2$
$a_2=18=2*3^2$
（最大公約数をを求めるときは素因数分解のカタチにしておくと楽です。素因数分解を利用した最大公約数の求め方は補講で）
ですから $a_2$ と $a_1$ の最大公約数は2です。

これだけではデータが足りないので $a_3$ と $a_2$ の最大公約数も調べてみます。
$a_3$ を求めるのは①より(2)の漸化式を利用したほうが簡単です。
漸化式より
$a_3=4a_2+a_1\\ \ \ \ \ =4*18+4\\ \ \ \ \ =2^2*19$
よって
$a_3$ と $a_2$ の最大公約数は2です。

おや・・・ $a_2$ と $a_1$ の最大公約数と同じ2になりましたね。
ひょっとしたらnに依存せず最大公約数は２になるのではないでしょうか。

この予想を確かめるため $a_4$ と $a_3$ の最大公約数を求めます。

以下、最大公約数を簡潔に表記するため記号を導入します。
2つの自然数a,b の最大公約数を
(a,b)
とすることとします。

$a_4=4a_3+a_2\\ \ \ \ \ =4^2\cdot19+18\\ \ \ \ \ =2^4\cdot19+2\cdot3^2\\ \ \ \ \ =2(2^3\cdot19+3^2)\\ \ \ \ \ =2\cdot7\cdot23$

よって
$(a_4,a_3)=2$
です。

どうやら予想は正しそうです。

ただ $a_4$ 以降の $a_n$ は数が大きくなって素因数分解が大変そうです。
素因数分解以外の方法で最大公約数を求められないでしょうか。

ここまでの調査より
$(a_4,a_3)=(a_3,a_2)=(a_2,a_1)=2$
と書けます。

この2数の最大公約数が連鎖していく形どこかで見覚えがありませんか。
そう、ユークリッドの互除法ですね。

A=QB+R（A,B,Qは非負整数、Rは0≦R≦B-1を満たす整数）
のとき
(A,B)=(B,R)
というアレです。

$a_{n+1},a_n$ にこのような関係式があれば互除法が適用できそうだと考えて式を探すと
ありますね。漸化式が。

$a_{n+1}=4a_n+a_{n-1}$
を
$a_{n+1}$ を $a_n$ で割った商が４、余りが $a_{n-1}$
とみなすことができれば（☆）
互除法より
$(a_{n+1},a_n)=(a_n,a_{n-1})・・・(a_3,a_2)=(a_2,a_1)=2$
となって $a_{n+1},a_n$ の最大公約数が２と求まります。

このみなし方は正しいのでしょうか。
互除法を見ると余りRの部分に制約がありますよね。
余りRは割る数Bよりも小さいという制約です。
漸化式において割る数は $a_n$ ,余りは $a_{n-1}$ としたのでした。
ここですべての自然数nについて $a_{n+1}＞a_n$ が言えれば制約が満たされみなし方（☆）の正しさが保証されます。
(3)より $a_n$ は自然数です。
$a_{n+1}=4a_n+a_{n-1}＞4a_n＞a_n$
ゆえにn≧2のとき, $a_{n+1}＞a_n$
これと $a_2＞a_1$ より、すべての自然数について $a_{n+1}＞a_n$ が言えました。
これで（☆）が正当化されました。
(4)が解けました。

解答の骨格

１． $a_n$ が増加列であること示す
２．漸化式に互除法を適用する
３．漸化式を繰り返し用いる

解答例

(3)よりすべての自然数 $n$ について $a_n$ は自然数
だから(2)の漸化式より $n≧2$ のとき
$a_{n+1}=4a_n+a_{n-1}＞a_n$
(1)より $a_2＞a_1$
よってすべての自然数 $n$ について $a_{n+1}＞a_n$ ・・・①

2つの自然数 $a,b$ の最大公約数を $(a,b)$ と表す
①より
$a_{n+1}=4a_n+a_{n-1} ( n≧2 )$
にユークリッドの互除法が適用できるから
$(a_{n+1},a_n)=(a_n,a_{n-1})$ ・・・②
②を繰り返し用いて
$(a_{n+1},a_n)=(a_n,a_{n-1})\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(a_{n-1},a_n-2)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(a_3,a_2)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(a_2,a_1)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =2$
よって求める最大公約数は $２$ である・・・（答）

まとめポイント

・2数の最大公約数を求める場合、素因数分解による方法とユークリッドの互除法による方法が考えられます。本問の場合、漸化式が互除法が適用できる形で与えられているため互除法がよいでしょう。
（ $a_{n+1}=4a_n^2+a_{n-1}$ のような形だったら互除法が適用できません）

・最大公約数の記号は
$GCD$
と書きます。（Greatest Common Divisor）の略です。
面倒くさい場合は単に()と表してよいでしょう。
いずれにせよ問題文で与えられていない記号を用いる場合には必ず答案上で記号を定義してください。
答案上で未定義の記号が現れると採点者には理解不能です。
採点者の忖度を期待してはいけません。
最悪の場合0点となります。

・互除法の適用に際して数列{a_n}が増加数列すなわち
$a_1＜a_2＜・・・・・a_n＜a_{n+1}$
を示したほうが確実です。

というのも数列{a_n}の項の大小関係が不明だと
$a_{n+1}=4a_n+a_{n-1}$
において $a_n≦a_{n-1}$ と解釈する余地が出てきてしまうためです。
$a_n≦a_{n-1}$ とすると
$a_{n-1}=qa_n+r$ ( $q$ は自然数、 $r$ は $0≦r≦a_{n-1}$ を満たす整数)
とおけます
このとき
$a_{n+1}=4a_n+a_{n-1}$
$=(4+q)a_n+r$
となりこれに互除法を適用することになって
$(a_{n+1},a_n)=(a_n,r)$
となってしまい $(a_n,a_{n-1})$ が求まりません。
これでは漸化式を繰り返し用いるという操作ができません。
つまり
$a_1＜a_2＜...＜a_{k-1}≧a_k＜...＜a_n＜a_{n+1}$
となる $K$ について
$(a_{n+1},a_n)=(a_n,a_{n-1})\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(a_{n-1},a_n-2)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \vdots\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(a_k+1,a_k)\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ =(a_k,r)$
となり $(a_{n+1},a_n)$ を求める過程の連鎖が途中で途切れることになります。
$(a_{n+1},a_n)$ から $(a_2,a_1)$ まで降下していくからこそ $a_{n+1}$ と $a_n$ の最大公約数が２だと結論できることを確認してください。

「(1)から(3)までで $a_n$ が増加数列となることは当たり前だ（だから書かなくてもよい）」
と感じる人がほとんどでしょうが、その当たり前のことを書くだけでこのような不条理が避けられるのですから書いたほうが安全です。

・思考過程で示したように求める最大公約数は2だと予想できます。
さらに漸化式が与えられていることから数学的帰納法を利用した解答が考えられます。
別解として示しておきます。

別解

$a_{n+1}$ と $a_n$ の最大公約数が $2$ であることを数学的帰納法で示す。

Ⅰ. $a_1=4,a_2=18$ より
　 $a_1$ と $a_2$ の最大公約数は $2$ である

Ⅱ. $n=k (k≧2)$ のとき, $a_k$ と $a_{k-1}$ の最大公約数を $2$ と仮定すると・・・（☆）
$a_k=2l,a_{k-1}=2m$ ( $l,m$ は互いに素) とおける
(2)の漸化式より
$a_k+1=4a_k+a_{k-1}\\ \ \ \ \ \ \ \ \ \ \ =2(4l+m)$

$4l+m$ と $l$ が互いに素でないとすると $2$ 以上の公約数 $g$ が存在して・・・（★）
$4l+m=pg,l=qg$ ( $p,q$ は自然数) と書ける
このとき,
$4l+m=pg\\ ⇔4qg+m=pg\\ ⇔m=(p-4q)g$
となり, $g$ は $m$ の約数
$l=qg$ より $g$ は $l$ の約数でもある
ゆえに $g$ は $l$ と $m$ の $2$ 以上の公約数となるがこれは $l$ と $m$ は互いに素であることに反する。
よって $4l+m$ と $l$ は互いに素
$a_k+1=2(4l+m),a_k=2l$
より $n=k+1$ のとき
$a_k+1$ と $a_k$ の最大公約数は $2$ である

Ⅰ.Ⅱ.よりすべての自然数 $n$ について
$a_{n+1}$ と $a_n$ の最大公約数は $2$ である

（別解終わり）

注１．帰納法の仮定（☆）と背理法の仮定（★）を混同しないようにしてください。
矛盾によって否定されるのは（★）であって（☆）ではありません。

注２．最大公約数を2と仮定したときの
$a_k=2l,a_{k_1}=2m$ における $l,m$ は互いに素です。
$l,m$ を単に自然数としてはいけません。
単に自然数としたのでは $l,m$ が公約数をもつ可能性が生じるため仮定した値2が最大公約数と言い切れくなります。

一般に2つの自然数 $a,b$ についてその最大公約数を $g$ とすると
$a=kg,b=lg$ （ $k,l$ は互いに素）
とおけます。

この置き方の使い方としては
2以上の最大公約数 $g$ を仮定してそれを否定することで2数が互いに素であることの証明に利用すことがほとんどです。
このとき $k,l$ が互いに素であることから矛盾を導きます。

別解の流れがまさに典型例です・
置き方だけでなく解答の流れを意識して理解してください。

最後に

(1)(2)(3)は簡単です。
定期テストレベルです。

(4)も漸化式からすぐに互除法の適用を思いついた人が多かったでしょう。
（思考過程にあるように私はすぐには思いつきませんでした。
　第一手に素因数分解を選択したことは本問の場合、悪手です。）
　

互除法の適用に際して ${a_n}$ が増加数列であることを答案上で明示するかどうかでは判断が分かれるところです。

巷に出回ってる解答例の大部分が ${a_n}$ が増加数列であることをを示さずに互除法を適用しています。
まとめポイントで示したように私は ${a_n}$ が増加数列であることを明示すべきと考えますが世間はそうではないようです。

開示された成績が軒並み高得点であることから察すると東大はそこまで厳密な解答は要求していないように思えます。
ですから ${a_n}$ が増加数列であることを明示せずに互除法を適用してもおそらく減点されていないでしょう。

それでも平素の学習では適用しようとしている定理の成立条件を確認することをオススメします。

補講　素因数分解を利用した最大公約数の求め方

・素因数分解を利用して2数の最大公約数を求める方法を確認しておきます。
　中学（小学校？）で学んだことなので忘れている人が多いです。

公約数とは2つ以上の数の共通の約数です。
約数とは数自身を割り切る数です。
素因数分解した形において約数は
各素因数のべき乗の積として現れます。
このとき、各素因数についてべき乗が0を下限とし、素因数分解の指数を上限として自由にとれることに注意してください。

$A=p_1^{a_1}p_2^{a_2}p_3^{a_3}$
$B=p_1^{b_1}p_2^{b_2}p_4^{b_4}$
( $p$ は素数、 $a,b$ は非負整数)とします。

Aの約数は
$p_1^xp_2^yp_3^z (0≦x≦a_1,0≦y≦a_2,0≦z≦a_3)$ ・・・①
となります。
（ここから約数の個数は $(x,y,z)$ の組の個数と同じことがわかります。
つまりAの約数の個数は $(a_1+1)(a_2+1)(a_3+1)$ 個です。）

具体例で示せば
$A=2^33^25$ のとき
$2^23^05^1=20$
はAの約数です。

同様にBの約数は
$p_1^lp_2^mp_4^n (0≦l≦b_1,0≦m≦b_2,0≦n≦b_4)$ ・・・②
となります。

公約数とはA,Bの共通の約数です。
①と②が同じ形になれば共通の約数といえます。

Ⅰ. Aの素因数 $p_3や$ Bの素因数 $p_4$ のような一方の数にしか含まれない素因数は同じ形になりようがないのでそのべき乗の指数は０です。

Ⅱ.　A,B共通の素因数 $p_1,p_2$ については素因数分解の指数の大小が関係します。
素因数 $p_1$ の指数 $a_1＞b_1$ のときを考えてみます。
このとき、 $a_1≧c＞b_1$ となる非負整数cが存在します。
Aの約数
$d=p_1^cp_2^yp^z$
は公約数になれるでしょうか？

Bは
$B=p_1^{b_1}p_2^{b_2}p_4^{b_4}$
で素因数 $p_1$ を $b_1$ 個持っています。
$c＞b_1$
よりdでBを割ると $p_1$ が $c-b_1$ 個余ってしまいます。
当然ながらこの余った $p_1$ は $p_1$ 以外の素因数を割ることはできません。
（素数の定義を思い出してください）
よってdはBを割り切ることができないのでdは公約数となれません。
このことからAの約数①で公約数となれるのは
$p_1^x (0≦x≦b_1)$
の形をしたものでありAとBを $p_1$ の指数で比べたとき大きくないほうの指数に上限が制約されることがわかります。
$p_1$ 以外の素因数についても話は同じです。