整数論の問題

1. 互除法で連分数展開を求める。
$$172=2\cdot 75+22,75=3\cdot 22+9,22=2\cdot 9+4,9=2\cdot 4+1,4=4\cdot 1$$
各段の商を順に並べると
$$\frac{172}{75}=[2;3,2,2,4]$$
となる（$n=4$、最後の項 $a_4=4\geqq 2$）。

2. 漸化式で近似分数を計算する。
$p_{-1}=1,p_{-2}=0,q_{-1}=0,q_{-2}=1$ として
$$p_k=a_k{p}_{k-1}+p_{k-2},q_k=a_k{q}_{k-1}+q_{k-2}$$
を用いる。
- $k=0$: $p_0=2,q_0=1$
- $k=1$: $p_1=3\cdot 2+1=7,q_1=3\cdot 1+0=3$
- $k=2$: $p_2=2\cdot 7+2=16,q_2=2\cdot 3+1=7$
- $k=3$: $p_3=2\cdot 16+7=39,q_3=2\cdot 7+3=17$
- $k=4$: $p_4=4\cdot 39+16=172,q_4=4\cdot 17+7=75$

最後の近似分数がもとの $\frac{172}{75}$ に一致することが確かめられる。

3. 検算。 公式 $p_n{q}_{n-1}-p_{n-1}{q}_n=(-1{)}^{n-1}$ で $n=4$ とすると
$$172\cdot 17-39\cdot 75=2924-2925=-1=(-1{)}^3$$
となり正しい。またこの式から $\gcd (39,17)=1$ もわかるので $\frac{39}{17}$ は既約である。

よって求める近似分数は $\frac{p_3}{q_3}=\frac{39}{17}$ である。

ユークリッドの互除法で連分数展開を求める。
$172=2\cdot 75+22$ より $a_0=2$。
$75=3\cdot 22+9$ より $a_1=3$。
$22=2\cdot 9+4$ より $a_2=2$。
$9=2\cdot 4+1$ より $a_3=2$。
$4=4\cdot 1+0$ より $a_4=4$。
よって $\frac{172}{75}=[2;3,2,2,4]$ で、最後の項は $a_4=4\geqq 2$ を満たし、$n=4$。

漸化式 $p_k=a_k{p}_{k-1}+p_{k-2}$, $q_k=a_k{q}_{k-1}+q_{k-2}$（$p_{-1}=1,q_{-1}=0,p_{-2}=0,q_{-2}=1$）で計算する。
$p_0/q_0=2/1$。
$p_1=3\cdot 2+1=7$, $q_1=3\cdot 1+0=3$。
$p_2=2\cdot 7+2=16$, $q_2=2\cdot 3+1=7$。
$p_3=2\cdot 16+7=39$, $q_3=2\cdot 7+3=17$。
$p_4=4\cdot 39+16=172$, $q_4=4\cdot 17+7=75$。これは $\frac{172}{75}$ と一致する。

検算として $[2;3,2,2]$ を直接計算する。$2+\frac{1}{3+\frac{1}{2+\frac{1}{2}}}=2+\frac{1}{3+\frac{2}{5}}=2+\frac{5}{17}=\frac{39}{17}$。これも一致する。
$39=3\cdot 13$, $17$ は素数なので既約である。

したがって $\frac{p_3}{q_3}=\frac{39}{17}$。