首都大学東京の文系数学では昨年、ユークリッドの互除法と３項間漸化式で定まる数列に関する整数問題が出題されましたが、今年は数学科でユークリッドの互除法をテーマとした重厚な証明問題が出題されました。
《問題》
以下の問いに答えなさい。
（１）正の整数 $p$、$q$、$f$ および整数 $r$ が次の関係を満たしているとする。$$p=fq+r$$ただし、$0 \leqq r < q$ とする。このとき整数 $d$ が $p$ と $q$ の公約数であることと、 $d$ が $q$ と $r$ の公約数であることは同値であることを示しなさい。
（２）正の整数 $k$、$m$ の最大公約数を $\text{gcd}(k,\ m)$ で表す。$p$、$q$ を $p>q$ を満たす正の整数とする。また、$n \geqq 2$ とし、$2n-1$ 個の正の整数 $f_1$、$f_2$、$\cdots$、$f_{n-1}$、$r_1$、$r_2$、$\cdots$、$r_n$ が次の関係を満たしているとする。
$\begin{align}& p=r_1 \\& q=r_2 \\& r_{1}=f_{1} r_{2} + r_{3} ,\ \ r_{3}<r_{2} \\& r_{2}=f_{2} r_{3} + r_{4} ,\ \ r_{4}<r_{3} \\& \ \ \ \ \ \vdots \\& r_{n-2}=f_{n-2} r_{n-1} + r_{n} ,\ \ r_{n}<r_{n-1} \\& r_{n-1}=f_{n-1}r_{n} \end{align}$
このとき、$\text{gcd}(p,\ q)=\text{gcd}(r_{j},\ r_{j+1})$（$j=1$、$2$、$\cdots$、$n-1$）が成り立つことを $j$ に関する数学的帰納法で示しなさい。
（３）$p$ と $q$ を互いに素な正の整数とする。このとき $ap+bq=1$ を満たす整数 $a$、$b$ が存在することを示しなさい。
（首都大学東京2018年(数学科) 第３問）
《考え方》
整数分野に慣れていないと難問に見えるかもしれません。せめて（１）と（２）は取りたいところです。
● ● ●
整数$d$が$p$と$q$の公約数であることを$\text{A}$、 $d$が$q$と$r$の公約数であることを$\text{B}$とします。
【$\text{A} \Rightarrow \text{B}$ の証明】
整数$d$が$p$と$q$の公約数なので、$p=d i_1$、$q=d i_2$（$i_1$、$i_2$は整数）と表せます。このとき関係式 $p=fq+r$ より、$$d i_1=f d i_2+r$$ $$\therefore d(i_1-i_2)=r$$となります。$i_1-i_2$ は整数ですから、$r$もまた$d$の倍数となり、$\text{B}$が言えます。
【$\text{A} \Leftarrow \text{B}$ の証明】
整数$d$が$q$と$r$の公約数なので、$q=d i_3$、$r=d i_4$（$i_3$、$i_4$は整数）と表せます。このとき関係式 $p=fq+r$ より、$$p=f d i_3+d i_4$$ $$\therefore p=d(i_3+i_4)$$となります。$i_3+i_4$ は整数ですから、$p$もまた$d$の倍数となり、$\text{A}$が言えます。
以上により、$\text{A} \iff \text{B}$ が示されました。
● ● ●
（１）の議論は任意の公約数について適用できるので、最大公約数についても同様のことが言えます。（２）では、（１）で示した性質を最大公約数に関して帰納的に利用することになります。
まず、$p=r_1$、$q=r_2$ より、$$\text{gcd}(p,\ q)=\text{gcd}(r_{1},\ r_{2})$$です。等式$$r_{1}=f_{1} r_{2} + r_{3} ,\ \ r_{3}<r_{2}$$において、（１）で証明した性質により、$$\text{gcd}(r_{1},\ r_{2})=\text{gcd}(r_{2},\ r_{3})$$が成り立ちます。したがって$$\text{gcd}(p,\ q)=\text{gcd}(r_{2},\ r_{3})$$が言えます。
ここで、$j=k$（$k$は$3$以上の整数）のとき$$\text{gcd}(p,\ q)=\text{gcd}(r_{k},\ r_{k+1}) \tag*{･･･(★)}$$が成り立っているとします。このとき等式$$r_{k}=f_{k} r_{k+1} + r_{k+2} ,\ \ r_{k+2}<r_{k+1}$$において同様に$$\text{gcd}(r_{k},\ r_{k+1})=\text{gcd}(r_{k+1},\ r_{k+2})$$が成り立ちます。$(★)$より、$$\text{gcd}(p,\ q)=\text{gcd}(r_{k+1},\ r_{k+2})$$が成り立つので、$(★)$は $j=k+1$ のときも成立します。よって帰納法により、最初の$2$本を除く $n-1$ 本の等式について$(★)$が成り立つことが示されます。
設問文に「$j$ に関する数学的帰納法で」とあるので、方針の立て方には苦労しないかと思います。
● ● ●
最大の難所は（３）でしょう。（２）で示した内容や手順が大きなヒントになっています。以下では（２）を利用するため、$p>q$ とします。また、
$\begin{align}& r_{1}=f_{1} r_{2} + r_{3} ,\ \ r_{3}<r_{2} \\& r_{2}=f_{2} r_{3} + r_{4} ,\ \ r_{4}<r_{3} \\& \ \ \ \ \ \vdots \\& r_{n-2}=f_{n-2} r_{n-1} + r_{n} ,\ \ r_{n}<r_{n-1} \\& r_{n-1}=f_{n-1}r_{n} \end{align}$
などの式が存在することは、$p$を$q$で割り算できること、ユークリッドの互除法が（この場合は、互いに素な）任意の整数で実行可能であるという事実に基づいています。$f_j$と$r_{j+2}$をそれぞれ、$r_j$を$r_{j+1}$で割ったときの商と余りとして帰納的に定義すれば、上記の等式群が存在することはほとんど自明です。なお、$r_j$は単調に減少するのでいつか必ず $r_j=0$ となるような $j$ が存在します。そのような $j$ を $n+1$ とすれば（２）の関係式と全く同様の設定で議論できます。いま、$p$、$q$は互いに素なので $\text{gcd}(p,\ q)=1$ であり、（２）より、$$\text{gcd}(p,\ q)=\text{gcd}(r_{n-1},\ r_{n})$$となりますから、最後の式$$r_{n-1}=f_{n-1}r_{n}$$において、$$r_{n}=1$$となります。
さて、$r_{1}=f_{1} r_{2} + r_{3}$ という等式は$$p-f_{1}q=r_{3}$$を満たすような整数$1$、$-f_{1}$が存在するということを主張しています。同様に、$r_{2}=f_{2} r_{3} + r_{4}$ という等式は$$-f_{2}p+(1+f_1 f_2)q=r_{4}$$を満たすような整数$-f_{2}$、$1+f_1 f_2$ が存在するということを主張しています。$r_5$や$r_6$についても同様に、
(整数)×$p$＋(整数)×$q$＝$r_j$
を満たす整数が存在することが分かります。先程説明した通り、$r_{n}=1$ となるので、$j=n$ のとき、
(整数)×$p$＋(整数)×$q$＝$1$
となるような整数が存在することが言えそうです。ここまで来れば、かなり見通しが良くなったかと思います。
ここで、整数${\alpha}_{j}$、${\beta}_{j}$を、等式$${\alpha}_{j} p + {\beta}_{j} q = r_j \tag*{･･･(☆)}$$を満たす整数とすることにします。$j=3$、$j=4$ のとき、そのような整数${\alpha}_{3}$、${\beta}_{3}$、および${\alpha}_{4}$、${\beta}_{4}$が存在することを確かめましたので、帰納法により一般の $j$ で$(☆)$を満たす整数${\alpha}_{j}$、${\beta}_{j}$が存在することが示せます。
$j=k$、$k+1$ のとき、$(☆)$を満たす整数${\alpha}_{j}$、${\beta}_{j}$が存在すると仮定します。すると、$$r_k = f_{k}r_{k+1} + r_{k+2}$$ $$\therefore {\alpha}_{k} p + {\beta}_{k} q = f_{k}({\alpha}_{k+1} p + {\beta}_{k+1} q) + r_{k+2}$$ $$\therefore ({\alpha}_{k}-f_k {\alpha}_{k+1})p + ({\beta}_{k}-f_{k}{\beta}_{k+1})q = r_{k+2}$$となり、${\alpha}_{k}-f_k {\alpha}_{k+1}$ および ${\beta}_{k}-f_{k}{\beta}_{k+1}$ はともに整数なので、これらをそれぞれ${\alpha}_{k+2}$、${\beta}_{k+2}$と置けば、$j=k+2$ のときも$(☆)$を満たす整数が存在することが言えます。
したがって帰納的に、任意の $j$ について$(☆)$を満たす整数${\alpha}_{j}$、${\beta}_{j}$が存在することが示されました。ただし $j>n$ の範囲では、${\alpha}_{j}$、${\beta}_{j}$はともに$0$とします。$j=1$、$j=2$ についても心配なら、$$\begin{cases}{\alpha}_{1}=1 \\ {\beta}_{1}=0\end{cases} \ \ \ \begin{cases}{\alpha}_{2}=0 \\ {\beta}_{2}=1 \end{cases}$$と定めておけば良いでしょう。
以上により、$${\alpha}_{n} p + {\beta}_{n} q = r_n \ (=1)$$を満たす整数${\alpha}_{n}$、${\beta}_{n}$が存在することが言えるので、$$ap+bq=1$$を満たす整数 $a$、$b$ が存在することが示されました。
（コメント）
（３）の出来具合で差の付く問題です。気付くべき重要なポイントとしては、
① $r_n=1$ である
② （２）の議論を下敷きにして $ap+bq=1$ という式が構成できる
でしょうか。昨年の文系数学の問題に比べるとかなりレベルアップしましたね。本問は恐らく長文の部類に入るでしょうが（２）までは見掛け倒しに過ぎません。こういう長めの文章題では、難しそうに見えて実は見掛け倒しに過ぎないという場合があります。見掛け倒しと分かったら、しっかり得点を搔き集めたいところです。
今回の問題はそれなりに文字数がありますが、確率や論証などの問題に比べたらマシな方です。特に確率の問題などは文字数が多いので、文字起こしする気になりませんね･･･(笑)。