皆さん二次試験お疲れ様でした！
明日も試験がある人は解答速報なんて見ずにさっさと寝ましょう(笑)。
国公立大のTopバッターはやはり東大でしょう。先程予備校の速報ページに掲載されたばかりの整数問題（文科理科ともに第４問）をお届けします。
《問題》
$p=2+\sqrt{5}$とおき、自然数 $n=1,2,3,\cdots$ に対して$$a_n=p^n+\left(-\dfrac{1}{p}\right)^n$$と定める。以下の問いに答えよ。ただし設問（１）は結論のみを書けばよい。
（１）$a_1$、$a_2$の値を求めよ。
（２）$n \geqq 2$とする。積 $a_1 a_n$ を、 $a_{n+1}$ と $a_{n-1}$ を用いて表せ。
（３）$a_n$ は自然数であることを示せ。
（４）$a_{n+1}$ と $a_n$ の最大公約数を求めよ。
（東京大学2017（共通）第４問）
問題の第一印象は「取り組みやすそう」でした。すべきことはワンパターンです。力のある受験生なら10分も要らないのではないでしょうか？
まず（１）ですが、$\dfrac{1}{p}$を有理化すると、$$\dfrac{1}{p}=\dfrac{1}{2+\sqrt{5}}=\sqrt{5}-2$$となるので、落ち着いて計算して $a_1=4$、$a_2=18$ と求められます。
次に（２）ですが、
$\begin{align} a_1 a_n &=\left( p-\dfrac{1}{p} \right) \left\{ p^n+\left( -\dfrac{1}{p} \right)^n \right\} \\ &=p^{n+1}+\left(-\dfrac{1}{p}\right)^{n+1}-p^{n-1}-\left(-\dfrac{1}{p}\right)^{n-1} \\ &=a_{n+1}-a_{n-1} \end{align}$
となりますので、$a_1 a_n=a_{n+1}-a_{n-1}$ と表すことができます。よって $a_1=4$ より、漸化式
$$a_{n+1}=4a_n+a_{n-1} \ \ (n \geqq 2)$$
を得ます。$a_1$、$a_2$ が自然数であることは分かっているので、この漸化式より帰納的にすべての $a_n$ が自然数であることが示せます。
（３）までは何も問題無いのですが、詰まるとすれば（４）でしょうか。まずは小さい $n$ で実験してみましょう。
$a_1=4$、$a_2=18$、$a_3=76$、$a_4=322$、$a_5=1364$
となっています（とりあえず $a_5$ くらいでやめておきましょう）。これより、$a_{n+1}$ と $a_n$ の最大公約数は「$2$」なのではないか？と予想することができます。これに気付けたら完答まで大きく前進したと言えます。
では$a_{n+1}$と$a_n$の最大公約数が$2$であるとして、その証明方法を考えましょう。最大公約数が$2$であるということは、
(＊)「$a_{n+1}$と$a_n$は$2$以外に公約数となる素因数を持たない」
ということを意味しています。
何を当たり前のことを言っているんだという気もしますが、この点に着目すると、$a_{n+1}$と$a_n$をそれぞれ$2$で割ってできる２つの数は「互いに素」であると言い換えることができます。つまり、数列$a_n$を$2$で割ってできる新しい数列$b_n$について、
「$b_{n+1}$と$b_n$が互いに素」 ⇔ (＊)
という関係が成り立つことに気付くことができます（ただし$b_n$は関係式$a_n=2 b_n$を満たす）。したがって「$b_{n+1}$と$b_n$が互いに素」であることを示せば良いことになるのです。
「ある数とある数が互いに素」であることを証明する問題のパターンには「$1$より大きい公約数を仮定して矛盾を導く」という背理法が有効です。
そこで$b_{n+1}$と$b_n$がともに$1$より大きい公約数 $d \ (>1)$ をもつと仮定しましょう。$b_n$は$a_n=2 b_n$を満たしますから、先程求めた$a_n$の漸化式に代入して$$b_{n+1}=4b_n+b_{n-1} \ \ (n \geqq 2)$$を得ます。仮定より、$b_{n+1}$と$b_n$はともに$d$の倍数ですからある自然数$k,l$を用いて$b_{n+1}=dk$、$b_n=dl$と表すことができます。よって漸化式より
$$dk=4dl+b_{n-1}$$
$$∴d(k-4l)=b_{n-1}$$
となり、$b_{n-1}$もまた$d$の倍数であることになります。これをどんどん繰り返していけば、結局$b_2$と$b_1$も$d$の倍数であることになります。ところが$a_2=18$、$a_1=4$でしたから、$b_2=9$と$b_1=2$となり$b_2$と$b_1$は互いに素です。これは$b_{n+1}$と$b_n$がともに$1$より大きい公約数 $d \ (>1)$ をもつという仮定に矛盾するので、そのような公約数$d$が存在することは不合理です。したがって$d=1$でなければなりませんから$b_{n+1}$と$b_n$は互いに素であることが示されました。
故に$a_{n+1}$と$a_n$は$2$以外に公約数となる素因数を持たないことが示されました。
以上より、求める最大公約数は $2$ となります。
解けてしまえば何ということもないですが、「公約数を仮定する」という整数分野の証明における基本が身に付いていないと完答は容易ではありません。（2017/02/26追記 河合塾の解答速報でも$a_n=2b_n$と置いて解いているようです）
しかしそれにしても最近の東大の整数問題は易化気味ですね･･･。他の問題との兼ね合いもありそうですが、この問題を落とすとかなり苦戦を強いられてしまうのではないでしょうか。これをリアルタイムで見ている東大受験者はいないと思いますが、明日の理科と英語も気を抜かず、最後まで諦めずに取り組んで欲しいと思います。
（類題：お茶の水女子大2009年 理系第2問）