【定理・公式・証明】高校数学定理・公式 – 数学A – ユークリッドの互除法

ユークリッドの互除法

証明

$a$ と $b$ の最大公約数が $g$ であるとき， $(a,b)=g$ と表す。

$(a,b)=g$ とすると，

$a=ga'$ ，$b=gb'$ ( $a',b'$ は互いに素な自然数)

とおける。 $a$ を $b$ で割った商を $q$ ，余りを $r$ とするとき，

$a=bg+r$

であるから，

$ga'=gb'q+r$

$r=g(a'-b'q)$

②において $a'-b’q$ は整数であるから， $r$ は $g$ の倍数である。一方， $b$ も $g$ の倍数であるから， $b$ と $r$ の最大公約数も $g$ の倍数となる。そこで，自然数 $m$ を用いて，

$(b,r)=gm$

とすると，

$b=gmb'',r=gnr'$ ( $b'',r'$ は互いに素な自然数)

とおけて，①より，

$a=gmb''q+gmr'$

$=gm(b''q+r')$

となる。

これより， $a,b$ はともに $gm$ の倍数であり， $(a,b)=g$ より， $m=1$

したがって，③より

$(b,r)=g$

であるから， $(a,b)=(b,r)$ すなわち， $a$ と $b$の最大公約数は， $b$ と $r$ の最大公約数に等しい。