整数論の問題

1. 連分数展開

ユークリッドの互除法を行う。
$$137=1\cdot 95+42,95=2\cdot 42+11,42=3\cdot 11+9,$$
$$11=1\cdot 9+2,9=4\cdot 2+1,2=2\cdot 1.$$
商を順に並べると
$$\frac{137}{95}=[1;2,3,1,4,2]$$
となる。

2. 近似分数の計算

$a_0=1,a_1=2,a_2=3,a_3=1,a_4=4,a_5=2$ とし、漸化式
$$p_n=a_n{p}_{n-1}+p_{n-2},q_n=a_n{q}_{n-1}+q_{n-2}$$
（$p_{-1}=1,q_{-1}=0,p_{-2}=0,q_{-2}=1$）で計算する。

• $n=0$: $p_0=1,q_0=1$
• $n=1$: $p_1=2\cdot 1+1=3,q_1=2\cdot 1+0=2$
• $n=2$: $p_2=3\cdot 3+1=10,q_2=3\cdot 2+1=7$
• $n=3$: $p_3=1\cdot 10+3=13,q_3=1\cdot 7+2=9$
• $n=4$: $p_4=4\cdot 13+10=62,q_4=4\cdot 9+7=43$
• $n=5$: $p_5=2\cdot 62+13=137,q_5=2\cdot 43+9=95$

確かに $p_5/q_5=137/95$ である。

3. 不定方程式の解

近似分数の基本性質 $p_n{q}_{n-1}-p_{n-1}{q}_n=(-1{)}^{n-1}$ を $n=5$ に適用すると
$$p_5{q}_4-p_4{q}_5=(-1{)}^4=1,$$
すなわち
$$137\cdot 43-95\cdot 62=5891-5890=1.$$
よって $(x,y)=(43,62)$ は解である。

$\gcd (137,95)=1$ より、一般解は整数 $t$ を用いて
$$x=43+95t,y=62+137t$$
と表される（$137(x-43)=95(y-62)$ から $95\mid x-43$ となるため）。$x>0$ かつ $y>0$ となるのは $t\geqq 0$ のときで、$x$ が最小になるのは $t=0$ のときである。

したがって求める組は $(x,y)=(43,62)$ である。

ユークリッドの互除法より、137 = 1·95 + 42、95 = 2·42 + 11、42 = 3·11 + 9、11 = 1·9 + 2、9 = 4·2 + 1、2 = 2·1。よって 137/95 = [1; 2, 3, 1, 4, 2]。

近似分数 p_k/q_k を漸化式 p_k = a_k p_{k-1} + p_{k-2}、q_k = a_k q_{k-1} + q_{k-2} で求める。
- k=0: 1/1
- k=1: 3/2
- k=2: 10/7
- k=3: 13/9
- k=4: 62/43
- k=5: 137/95

隣り合う近似分数について p_k q_{k-1} − p_{k-1} q_k = (−1)^{k-1} が成り立つ。k=5 では 137·43 − 62·95 = 5891 − 5890 = 1 となる。したがって (x,y) = (43,62) は 137x − 95y = 1 を満たす。

一般解は x = 43 + 95t、y = 62 + 137t（t は整数）。x と y がともに正の整数で x が最小になるのは t=0 のときで、(x,y) = (43,62)。t=−1 では x<0 となるので不適。

検算：137·43 = 5891、95·62 = 5890、差は 1 で正しい。