ユークリッドの互除法

大きい方の数 $84$ を、小さい方の数 $30$ で割ります。

$84 = 30 \times 2 + 24$

$30 \times 2 = 60$ で、$84 - 60 = 24$ なので、商は $2$、余りは $24$ です。余りが $0$ ではないので、次は $30$ と $24$ の組で割り算をします。

$30 = 24 \times 1 + 6$

商は $1$、余りは $6$ です。余りが $0$ ではないので、次は $24$ と $6$ の組で割り算をします。

$24 = 6 \times 4 + 0$

$6 \times 4 = 24$ なので、余りがちょうど $0$ になりました。このときの割る数である $6$ が、求める最大公約数です。

$\gcd(84, 30) = 6$

（確認）$84 = 2^2 \times 3 \times 7$、$30 = 2 \times 3 \times 5$ なので、共通な素因数は $2^1 \times 3^1 = 6$ です。互除法の結果と一致しています。

答え $6$

$1071$ を $1029$ で割ります。

$1071 = 1029 \times 1 + 42$

商は $1$、余りは $42$ です（$1071 - 1029 = 42$）。余りが $0$ ではないので、次は $1029$ と $42$ の組で割り算をします。

$1029 = 42 \times 24 + 21$

$42 \times 24 = 1008$ で、$1029 - 1008 = 21$ なので、商は $24$、余りは $21$ です。余りが $0$ ではないので、次は $42$ と $21$ の組で割り算をします。

$42 = 21 \times 2 + 0$

余りが $0$ になりました。このときの割る数である $21$ が最大公約数です。

$\gcd(1071, 1029) = 21$

このように、$1071$ や $1029$ を自分で素因数分解しなくても、割り算を3回繰り返すだけで最大公約数が求められました。これが互除法の便利なところです。

次に、この最大公約数 $21$ を使って分数を約分します。分子と分母をそれぞれ $21$ で割ります。

$1071 \div 21 = 51, \qquad 1029 \div 21 = 49$

よって、

$\frac{1071}{1029} = \frac{51}{49}$

最大公約数(分子と分母に共通するいちばん大きい約数)ですでに割ったので、$51$ と $49$ にはもう共通の約数($1$以外の約数)は残っていません。実際、$51 = 3 \times 17$、$49 = 7^2$ であり、共通の素因数はないので、$\dfrac{51}{49}$ が既約分数です。

答え 最大公約数は $21$、既約分数は $\dfrac{51}{49}$

具体的な数ではなく文字 $n$ が入っていますが、考え方はこれまでと同じです。「大きい方を小さい方で割って、商と余りを求める」という操作を、文字式のまま行っていきます。

ステップ1 $3n+2$ を $2n+1$ で割る

商を $1$ とおいて確かめてみます。

$1 \times (2n+1) + (n+1) = 2n + 1 + n + 1 = 3n+2$

たしかに $3n+2$ に一致するので、商は $1$、余りは $n+1$ です。

$3n+2 = 1 \times (2n+1) + (n+1)$

この余り $n+1$ が正しい余り(割る数である $2n+1$ より小さい)になっているかも確認します。$n$ は $1$ 以上の自然数なので、$n+1 \ge 2 > 0$ です。また、$n+1 < 2n+1$ を整理すると $0 < n$ となり、これも $n \ge 1$ から成り立っています。したがって、$0 \le n+1 < 2n+1$ が確かめられ、商 $1$・余り $n+1$ で正しいことが分かります。

互除法の性質より、

$\gcd(3n+2,\ 2n+1) = \gcd(2n+1,\ n+1)$

ステップ2 $2n+1$ を $n+1$ で割る

同じように商を $1$ とおいて確かめます。

$1 \times (n+1) + n = n+1+n = 2n+1$

一致するので、商は $1$、余りは $n$ です。

$2n+1 = 1 \times (n+1) + n$

余りの条件 $0 \le n < n+1$ も、$n$ が自然数(あるいは $0$)であれば常に成り立ちます。よって、

$\gcd(2n+1,\ n+1) = \gcd(n+1,\ n)$

ステップ3 $n+1$ と $n$ の最大公約数を考える

$n+1$ と $n$ は、差がちょうど $1$ である2つの整数(連続する整数)です。ここで、ある整数 $d$ が $n+1$ と $n$ の両方を割り切る(公約数である)とします。すると、$d$ は2つの数の差である

$(n+1) - n = 1$

も割り切ることになります。$1$ を割り切ることができる正の整数は $1$ しかありません。したがって $d = 1$ となり、$n+1$ と $n$ の公約数は $1$ 以外にありえないことが分かります。つまり、

$\gcd(n+1,\ n) = 1$

まとめ

ステップ1〜3をつなげると、

$\gcd(3n+2,\ 2n+1) = \gcd(2n+1,\ n+1) = \gcd(n+1,\ n) = 1$

となります。

（確認)$n=1$ のとき $3n+2=5$、$2n+1=3$ で $\gcd(5,3)=1$。$n=3$ のとき $3n+2=11$、$2n+1=7$ で $\gcd(11,7)=1$。どちらも答えと一致しています。

答え どんな自然数 $n$ に対しても、$\gcd(3n+2, 2n+1) = 1$(常に互いに素)

$315 = 273 \times 1 + 42$ $273 = 42 \times 6 + 21$ $42 = 21 \times 2 + 0$

よって、

$\gcd(315, 273) = 21$