ユークリッドアルゴリズム

$\displaystyle\frac{50}{23}=2+\displaystyle\frac{4}{23}$

$\displaystyle\frac{23}{4}=5+\displaystyle\frac{3}{4}$

$\displaystyle\frac{4}{3}=1+\displaystyle\frac{1}{3}$

この計算方法をユークリッドのアルゴリズムとよびます。まとめると、

$\displaystyle\frac{50}{23}=2+\displaystyle\frac{4}{23}=2+\displaystyle\frac{1}{\displaystyle\frac{23}{4}}=2+\displaystyle\frac{1}{5+\displaystyle\frac{3}{4}}=2+\displaystyle\frac{1}{5+\displaystyle\frac{1}{\displaystyle\frac{4}{3}}}=2+\displaystyle\frac{1}{5+\displaystyle\frac{1}{1+\displaystyle\frac{1}{3}}}$

となりますので、すなわち $2+\displaystyle\frac{1}{5+\displaystyle\frac{1}{1+\displaystyle\frac{1}{3}}}=\frac{50}{23}$ となります。

最後の $\displaystyle\frac{1}{3}$ を消去すると、 $2+\displaystyle\frac{1}{5+\displaystyle\frac{1}{1}}=\displaystyle\frac{13}{6}$ となりますが、これらは $13*23=299 , 50*6=300$ より $50*6-23*13=1$ を満たすので $50x+23y=1$ の整数解を与えています。

上の計算の意味するところは連分数の理論によって説明することができます。

$a_0+\displaystyle\frac{1}{a_1+\displaystyle\frac{1}{\cdots+\displaystyle\frac{1}{a_n}}}=\displaystyle\frac{p_n}{q_n}$ とおく。このとき、
$\displaystyle\frac{p_{n+1}}{q_{n+1}}=\displaystyle\frac{a_{n+1}p_{n}+p_{n-1}}{a_{n+1}q_{n}+q_{n-1}}$ が成り立つ。（ $n \geqq 1$ ）

k56737kagawa.hatenablog.com

$p_{n+1}q_{n}-p_nq_{n+1}=(a_{n+1}p_n+p_{n-1})q_n-p_n(a_{n+1}q_n+q_{n-1})$ $=p_{n-1}q_n-p_nq_{n-1}=p_0q_1-p_1q_0orp_1q_0-p_0q_1=\pm(a_0a_1-(a_0a_1+1))=\pm 1$