今日は首都大学東京の整数問題です。理系では出題されなかったようですが、良い問題です。
《問題》
数列$\{a_n\}$を次の条件によって定める。
$a_1=1$、$a_2=2$、$a_{n+2}=2a_{n+1}+a_n \ (n=1,2,3,\cdots)$
以下の問いに答えよ。
（１）$a_3、a_4、a_5$を求めなさい。
（２）$x$、$y$ についての１次不定方程式 $a_5 x+a_4 y=1$ の整数解をすべて求めなさい。
（３）すべての自然数$n$に対して、$a_{n+1}$と$a_n$が互いに素であることを示しなさい。
（首都大学東京2017 前期文系第４問）
《考え方》
（１）は特に言うことはありません。（２）は１次不定方程式
「$ax+by=1$」
が解を持つことと、係数$a、b$が互いに素であることが同値であるという関係をモチーフにしている問題ですが、そんな事は知らなくても大丈夫です。
$a_3=5$、$a_4=12$、$a_5=29$となるので１次不定方程式 $$29x+12y=1 \tag{1}$$ の整数解をすべて求めればよいことになります。頑張って解の一つ$(x,y)=(5,-12)$を見つければこっちのもの。$$29 \cdot 5+12 \cdot (-12)=1 \tag{2}$$を$(1)$から引くと$$29(x-5)+12(y+12)=0$$ $$\therefore 29(x-5)=-12(y+12)$$となります。$29$と$12$は互いに素であり$x-5$、$y+12$は任意の整数値をとるので、ある整数$m、n$を用いて$$x-5=12m、y+12=29n$$と表せます。ここで$(1)$より$29 \cdot 12 m=-12 \cdot 29 n$ですから、$n=-m$です。よって$$\begin{cases} x=12m+5 \\ y=-29m-12 \end{cases} \ (m \in \mathbb{Z})$$が求めるすべての整数解となります。
続いて（３）ですが、これは帰納法の出番です。$a_{n+1}$と$a_n$の最大公約数を$d$と置きます。漸化式 $a_{n+2}-2a_{n+1}=a_n$ より左辺は$d$の倍数ですから$a_n$も$d$の倍数となります。これを繰り返していくと$a_1=1$が$d$の倍数でなければならないので $d=1$ しかあり得ません。故に$a_{n+1}$と$a_n$が互いに素であることが示されました。
（コメント）
（２）を当てずっぽうで解こうとすると大変です。そういう時に活躍するのが置き換えです。例えば$(1)$を$$12(2x+y)+5x=1$$と変形して $2x+y=s$ と新しい整数に置き換えると、$$12s+5x=1$$と大分簡単になります。これをさらに簡単にしましょう。$$2s+5(2s+x)=1$$と変形して $2s+x=t$ と新しい整数に置き換えると、$$2s+5t=1$$となり、もっと簡単になりました。これは明らかに$(s,t)=(-2,1)$を解に持ちますから、これを代入してできる連立方程式$$\begin{cases} 2x+y=-2 \\ -4+x=1 \end{cases}$$を解いて、結局$(x,y)=(5,-12)$を得ることができます。また、変形の途中で式の係数が数列$\{a_n\}$の第$1$～$3$項になっているのは偶然ではありません。なぜならば、上記の式変形は単に数列$\{a_n\}$の漸化式を利用しているにすぎないからです（$a_5 x+a_4 y=1$を$(2a_4 +a_3) x+a_4 y=1$というふうに変形しているだけです）。これらの計算を解答用紙に書く必要は無いですが、１次不定方程式を解く際に何かと便利な方法なので覚えておきましょう。
今年の東大にも本問の類題がありましたね。来年以降も同様の問題が出題される可能性は大なので、受験生の方は是非とも対策をしておくべきでしょう。