連分數

輾轉相除法(III) (Euclidean algorithm)
國立蘭陽女中數學科陳敏晧老師

連結：輾轉相除法(II)

一、輾轉相除法與連分數

首先讓我們來練習一下輾轉相除法，求 $$(42897, 18644)=\underline{~~~~~~~~~~~~~~~}$$。
（1）橫式過程：

$$42897=2\times 18644+5609$$
$$18644=3\times 5609+1817$$
$$5609=3\times 1817+158$$
$$1817=11\times 158+79$$
$$158=2\times 79+0$$

$$\therefore \left( {42897,18644} \right) = \left( {18644,5609} \right) = \left( {5609,1817} \right) = \left( {1817,158} \right) = \left( {158,79} \right) = \left( {79,0} \right) = 79$$