% 例題A4.2.1：ユークリッドの互除法 （One More）★
(1)ユークリッドの互除法を用いて,357と544の最大公約数と最小公倍数を求めよ. (2)ユークリッドの互除法を用いて,$\frac{638}{899}$を既約分数にせよ.
% 解答（例題A4.2.1）
(1)$$\begin{aligned} 544 &=357 \times 1+187 \\ 357 &=187 \times 1+170 \\ 187 &=170 \times 1+17 \\ 170 &=17 \times 10 \end{aligned}$$170と17の最大公約数は17であるから,357と544の最大公約数は,17 したがって,$357=21 \times 17,544=32 \times 17$よって,357と544の最小公倍数は,$$21 \times 32 \times 17=11424$$(2)$$\begin{aligned} 899 &=638 \times 1+261 \\ 638 &=261 \times 2+116 \\ 261 &=116 \times 2+29 \\ 116 &=29 \times 4 \end{aligned}$$116と29の最大公約数は29であるから,638と899の最大公約数は,29 よって,$\frac{638}{899}=\frac{29 \times 22}{29 \times 31}=\frac{22}{31}$
% 問題A4.2.1
(1)ユークリッドの互除法を用いて,462と700の最大公約数と最小公倍数を求めよ. (2)ユークリッドの互除法を用いて,$\frac{871}{1209}$を既約分数にせよ.
% 解答A4.2.1
(1)$$\begin{aligned} 700 &=462 \times 1+238 \\ 462 &=238 \times 1+224 \\ 238 &=224 \times 1+14 \\ 224 &=14 \times 16 \end{aligned}$$224と14の最大公約数は14であるから,462と700の最大公約数は,14 したがって,$462=33 \times 14,700=50 \times 14$よって,462と700の最小公倍数は,$$33 \times 50 \times 14=23100$$(2)$$\begin{aligned} 1209 &=871 \times 1+338 \\ 871 &=338 \times 2+195 \\ 338 &=195 \times 1+143 \\ 195 &=143 \times 1+52 \\ 143 &=52 \times 2+39 \\ 52 &=39 \times 1+13 \\ 39 &=13 \times 3 \end{aligned}$$39と13の最大公約数は13であるから,871と1209の最大公約数は,13 よって,$\frac{871}{1209}=\frac{13 \times 67}{13 \times 93}=\frac{67}{93}$
