ユークリッドの互除法
整数(教科書範囲) ★★
ユークリッドの互除法と互助法の原理について扱います．
ユークリッドの互除法
唐突ですが，縦 $345 \rm{cm}$ ，横 $506 \rm{cm}$ の長方形の部屋を敷き並べることができる正方形のタイルの最大の一辺の長さはいくつでしょうか．
この答えが，( $\boldsymbol{345}$ と $\boldsymbol{506}$ の最大公約数)であることは容易です．
しかし，$345$ と $506$ は数が大きいので普通に計算すると少々大変です．
ユークリッドの互除法のイメージ
最大公約数を求めるために，長方形内の最大の正方形を作り，余った長方形を考えます．
余った長方形を敷き並べることができる正方形のタイルで，左の正方形も並べることができるので，
( $\boldsymbol{506}$ と $\boldsymbol{345}$ の最大公約数)
$\boldsymbol{=}$ ( $\boldsymbol{345}$ と $\boldsymbol{161}$ の最大公約数)
が言えます．これを互除法の原理と言います．
互除法の原理を繰り返せば，数字が小さくなって，最大公約数を見つけやすいはずです．先ほどの右の長方形に同じことを繰り返し適用します．
つまり
( $506$ と $345$ の最大公約数)
$=$ ( $345$ と $161$ の最大公約数)
$=$ ( $161$ と $23$ の最大公約数) $=23$
こうして最大公約数を求めることができました．答えは $\boldsymbol{23 \ \rm cm}$ です．
こうして互除法の原理を繰り返して最大公約数を求める手法をユークリッドの互除法といいます．
互除法の原理
上で紹介した互除法の原理と証明です．
原理と言っても，高校範囲で証明できる定理です．
互除法の原理
自然数 $a$ を 自然数 $b$ で割ったときの余りを $r$ とすると
$\boldsymbol{\gcd (a,b)=\gcd (b,r)}$
ただし，$\gcd (a,b)$ は $a$ と $b$ の最大公約数を表す．
互除法の原理の証明
証明
$a$ を $b$ で割ったときの商を $q$，$\gcd (a,b)=g$，$a=ga'$，$b=gb'$ ( $a'$ と $b'$ は互いに素)とすると
$a=bq+r$
$\Longleftrightarrow r=a-bq$
$\Longleftrightarrow r=g(a'-b'q)$
より $g$ は $r$ の約数．$g$ は $b$ の約数でもあるので，$g$ は $b$ と $r$ の公約数である．これより $\gcd (b,r)=gk$ とおけるので，$b=gkb''$，$r=gkr'$ とすると
$a=bq+r$
$\Longleftrightarrow ga'=gk(b''q+r')$
$\Longleftrightarrow a'=k(b''q+r')$
より $a'$ は $k$ の倍数．$b=gb'=gkb'' \ \Longleftrightarrow \ b'=kb''$ より $b'$ も $k$ の倍数．$a'$ と $b'$ は互いに素より $k=1$．
$\therefore \ \gcd (a,b)=\gcd (b,r)$
※ この証明は例えば2019年順天堂大学医学部で出題されています．
例題と練習問題
例題
例題
$345$ と $506$ の最大公約数を求めよ.
講義
上の例の数字を再度使います．大きい数 $\div$ 小さい数をして，再利用するように書いていきます．
解答と解説
普通に割り算をします．書くときになるべく右に書くようにします．
$345$ を今出てきた余りである $161$ で割ります．
同様に $161$ を今出てきた余りである $23$ で割ります．
余りが $0$ になったら終わりで，1番左に書いてある数字(最後に割る数)が答えになります．
$\therefore \ \gcd (345,506)=\boldsymbol{23}$
練習問題
練習
(1) $310$ と $837$ の最大公約数を求めよ.
(2) $629$ と $459$ の最大公約数を求めよ.
練習の解答
(1)
$\therefore \ \gcd (310,837)=\boldsymbol{31}$
(2)
$\therefore \ \gcd (629,459)=\boldsymbol{17}$