ユークリッドの互除法における割り算の回数を絡めた整数問題です。初見の受験生にとっては掴み所の無い問題に感じられたかもしれません。
《問題》
$0$以上の整数 $x$、$y$ に対して $R(x,\ y)$ を次のように定義する。
$$\begin{cases} xy=0 \text{のとき、} R(x,\ y)=0 \\ xy \ne 0 \text{のとき、} x \text{を} y \text{で割った余りを} R(x,\ y) \text{とする。} \end{cases}$$
正の整数 $a$、$b$ に対して数列 $\{r_n\}$ を次のように定義する。
$r_1=R(a,\ b)$、$r_2=R(b,\ r_1)$、$r_{n+1}=R(r_{n-1},\ r_{n}) \ \ (n=2,\ 3,\ 4, \cdots)$
また、$r_n=0$ となる最小の $n$ を $N$ で表す。例えば $a=7$、$b=5$ のとき $N=3$ である。
次に、数列 $\{f_n\}$ を次のように定義する。
$f_1=f_2=1、f_{n+1}=f_n+f_{n-1}\ (n=2,\ 3,\ 4,\ \cdots)$
このとき以下の各問いに答えよ。
（１）$a=f_{102}$、$b=f_{100}$ のとき、$N$ を求めよ。
（２）正の整数 $a$、$b$ について、$a$ が $b$ で割り切れないとき、$r_1 \geqq f_N$ が成立することを示せ。
（３）$2$以上の整数 $n$ について、$10 f_n < f_{n+5}$ が成立することを示せ。
（４）正の整数 $a$、$b$ について、$a$ が $b$ で割り切れないとき、$$\displaystyle \sum^{N-1}_{k=1} \dfrac{1}{r_k}<\dfrac{259}{108}$$が成立することを示せ。
（東京医科歯科大学2018年 (医)第１問）
実際の試験問題には訂正がありました（注：ここでは修正済みの設問文を掲載しています）。なお、歯学部では以下のような設問が出題されましたが、本稿では専ら医学部の問題について解説していきます。
» 歯学部の問題はこちら
《歯学部》
（１）$a=33$、$b=26$ のとき、$N$ を求めよ。
（２）$a=f_{30}$、$b=f_{29}$ のとき、$N$ を求めよ。
（３）正の整数 $a$、$b$ が $N=5$ を満たすとき $r_1 \geqq f_5$ を示せ。
（４）正の整数 $a$、$b$ について、$a$ が $b$ で割り切れないとき、$b \geqq f_{N +1}$ が成立することを示せ。
» 閉じる
《考え方》
● ● ●
$a=f_{102}$、$b=f_{100}$ のとき、$$\begin{align} r_1 &= R(f_{102},\ f_{100}) \\ &=R(2f_{100}+f_{99},\ f_{100}) \\ &=f_{99} \end{align}$$となります。同様にして$r_2=f_{98}$、$r_3=f_{97}$、$\cdots$ となります。$$f_{n+1}=f_{n}+f_{n-1},\ f_{n}>f_{n-1}$$より、常に$$R(f_{n+1},\ f_{n})=f_{n-1}$$となることが言えます。これより、$$\begin{cases} r_{98}=R(f_{4},\ f_{3})=R(3,\ 2)=1 \\ r_{99}=R(f_{3},\ f_{2})=R(2,\ 1)=0 \end{cases}$$となるので、$$\color{red}{N=99}$$と求められます。
● ● ●
（２）はなかなか目の付け所が難しい問題です。ここで詰まった受験生は多かったかもしれませんね。
示すべきは $r_1 \geqq f_N$ ですが、これはどういう意味を持った式なのでしょうか。日本語に直せば、「$a$を$b$で割ったときの余りが$f_N$より大きい」となります。これでもイマイチピンと来ないかもしれません。ここで$N$というのは $r_n=0$ となる最小の $n$ を指しています。これはユークリッドの互除法で割り算をする最大の回数のことです。取り敢えずは$f_N$と余り$r_j$の関係を調べましょう。
$r_1$は$a$を$b$で割ったときの余りでした。$r_2$や$r_3$なども同様に定義されており、割り算の関係式$$r_1=r_2 q_1+r_3$$より、$$r_1 \geqq r_2+r_3$$が言えます。同様に$$r_2 \geqq r_3+r_4$$や、$$r_3 \geqq r_4+r_5$$などが成り立ちます。ここでこれらの等式の形に注目すると、数列$f_n$（フィボナッチ数列）の漸化式において、等号を不等号に変えた形になっていることが分かります。これに着想して $r_1 \geqq f_N$ だけでなく、$r_2 \geqq f_{N-1}$、$r_3 \geqq f_{N-2}$、$\cdots$が成り立つのではないか、と推測することができます。実際、（１）ではこれらの関係が成立していますし、適当な整数の組で試しても成り立っていそうです。種明かしをすると、これらすべての不等式について辺々の和を取れば目的の式が得られる、という寸法になっているのです。このことを証明しましょう。
これから証明するのは「$1 \leqq n \leqq N-1$ を満たすすべての$n$について、$$r_{N-n} \geqq f_{n+1}$$が成立すること」です。
《証明》
$n=1$ のとき$$r_{N-1} \geqq 1 =f_2$$より、成立している。また、$r_{N-2}>r_{N-1} \geqq 1$ より $r_{N-2} \geqq 2$ であるから、$n=2$ のとき $$r_{N-2} \geqq 2=f_3$$となり成立している。
$n=k$、$k+1$（$k$は $3 \leqq k \leqq N-2$ を満たす整数）のとき、$$r_{N-k} \geqq f_{k+1},\ \ r_{N-(k+1)} \geqq f_{k+2}$$がともに成立していると仮定する。このとき仮定より、$$r_{N-(k+2)} \geqq r_{N-(k+1)}+r_{N-k} \geqq f_{k+1}+f_{k+2}=f_{k+3}$$が成り立つ。故に $n=k+3$ でも成立するから数学的帰納法により$1 \leqq n \leqq N-1$ を満たすすべての$n$について、$$r_{N-n} \geqq f_{n+1}$$が成立することが示された。
□
以上により、$n=N-1$ とすれば、$$r_1 \geqq f_N$$が導かれます。この結果は正の整数 $a$、$b$ の取り方によらないので、題意を示すことができました。
● ● ●
（３）は単なる計算で片付きます。もし（２）で解答が難しくなったら飛ばして（３）を先にやるというのもアリです。設問を飛ばしたからといって減点されるなんてことは普通ありませんので、その辺は安心して下さい(笑)。
$$\begin{align} f_{n+5} &=f_{n+4}+f_{n+3} \\ &=2f_{n+3}+f_{n+2} \\ &=3f_{n+2}+2f_{n+1} \\ &=5f_{n+1}+3f_{n} \\ &=8f_{n}+5f_{n-1} \\ &=13f_{n}+5f_{n-2} \\ &> 10 f_{n} \end{align}$$
より、$f_{0}=0$ と置けばこれは$2$以上の整数$n$で成立します。よって不等式$$10 f_n < f_{n+5}$$が示されました。
● ● ●
最後の設問です。ここで（２）の議論が活きてきます。方針としては前問までの結果を利用することになります。ただ、（３）の誘導に乗らず、漸化式からフィボナッチ数列の一般項を求めてゴリゴリ計算しても良いのですが、よほど数学力があるわけでもない限り、時間の浪費になってしまいます。
さて、（２）より、$1 \leqq n \leqq N-1$ を満たすすべての$n$について、$$r_{N-n} \geqq f_{n+1}$$が成立することが示されているので、両辺の逆数をとると$$\dfrac{1}{r_{N-n}} \leqq \dfrac{1}{f_{n+1}}$$となります。これより、
$$\displaystyle \sum^{N-1}_{k=1} \dfrac{1}{r_k} \leqq \displaystyle \sum^{N-1}_{k=1} \dfrac{1}{f_{k+1}}$$
が言えます。この右辺を何とかして$\dfrac{259}{108}$以下の数で評価します。そこで（３）で示した不等式の利用を考えます。$10 f_n < f_{n+5}$ より、両辺の逆数をとると$$\dfrac{1}{f_{n+5}} < \dfrac{1}{10 f_n}$$となります。
ここで、整数$m$を用いて $5m+2$ と表せる$N$以下の最大の整数を $M \ (=5m+2)$ とし、簡単のため$$S=\left( \dfrac{1}{f_{2}}+\dfrac{1}{f_{3}}+\cdots+\dfrac{1}{f_{6}} \right)=\dfrac{259}{120}$$と置きます。これにより、次のように計算することができます。
$\begin{align}& \ \ \ \ \ \displaystyle \sum^{N-1}_{k=1} \dfrac{1}{f_{k+1}} \\
&= \left( \dfrac{1}{f_{2}}+\dfrac{1}{f_{3}}+\cdots+\dfrac{1}{f_{6}} \right) \\ &\ \ \ \ \ +\left( \dfrac{1}{f_{7}}+\dfrac{1}{f_{8}}+\cdots+\dfrac{1}{f_{11}} \right) \\ &\ \ \ \ \ \ \ \ \ \ +\cdots \\ &\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ + \left( \dfrac{1}{f_{M}}+\cdots+\dfrac{1}{f_{N}} \right) \\
&<S+\left( \dfrac{1}{10}+\dfrac{1}{10}+\cdots+\dfrac{1}{10} \right)S \\ &\ \ \ \ \ +\left( \dfrac{1}{10^2}+\dfrac{1}{10^2}+\cdots+\dfrac{1}{10^2} \right)S \\ & \ \ \ \ \ \ \ \ \ \ +\cdots + \left( \dfrac{1}{f_{M}}+\cdots+\dfrac{1}{f_{M+4}} \right) \\ &=\left(1+\dfrac{1}{10}+\dfrac{1}{10^2}+\cdots+\dfrac{1}{10^m} \right)S \\ &= 1 \cdot \dfrac{1-\left(\dfrac{1}{10}\right)^m}{1-\dfrac{1}{10}}S \\ &<\dfrac{10}{9}S \\ &=\dfrac{10}{9} \cdot \dfrac{259}{120} \\ &=\dfrac{259}{108} \end{align}$$
故に$$\displaystyle \sum^{N-1}_{k=1} \dfrac{1}{r_k}<\dfrac{259}{108}$$が成立することが示されました。途中式の見かけは少し仰々しいですが、中身はそれほど複雑ではありません。$\dfrac{1}{f_{N}}$の部分を評価する際は、項を余分に多く取って評価しないといけないことに注意しましょう。
（コメント）
流石に医科歯科大レベルになると書くことが増えますね(笑)。ごちゃごちゃと書いてきましたが、基本は不等式による評価です。誘導に乗ることの重要性を感じ取って頂ければと思います。
なお、（２）を解答する際に、目的の $r_1 \geqq f_N$ という不等式だけでなく、より一般に「$1 \leqq n \leqq N-1$ を満たすすべての$n$について、$r_{N-n} \geqq f_{n+1}$ が成立すること」を証明しました。一見冗長に見えるかもしれませんが、これは（４）を見据えた解法となっており、実際の試験において実践するにはかなり高度な考え方と言えます。勿論、数学が得意な方であれば、悩むことなく解いてしまうのでしょうが･･･。
数学愛好家の間では広く知られている内容だと思いますが、
「ユークリッドの互除法で２数 $p$、$q$（$p>q$）の最大公約数を得るまでに要する割り算の回数は、$q$の$10$進記数における桁数を$N$とすると、高々$5N$以下である」
という面白い定理があります。これはガブリエル・ラメ（Gabriel Lamé：1795年～1870年）というフランスの数学者が発表したので「ラメの定理」と呼ばれています。この定理はアルゴリズム論ではしばしば見かけるもので、その証明にはフィボナッチ数列が深く関わっています。
これに付随して、ユークリッドの互除法において最も計算に手間のかかる数の組み合わせが、隣接するフィボナッチ数の組であることも示すことができます。興味のある方は証明してみて下さい！