【数A】ユークリッドの互除法【整数の性質（第4回）】

2つの数の最大公約数を求めるときにそれぞれ素因数分解して求めること方法は以前に学習していますが、素因数の数が大きい数の場合，素因数分解は簡単ではない．ここでは，素因数分解を使用せずに、整数の割り算とあまりから最大公約数を求める方法について学習します。

割り算と最大公約数

2つの自然数の最大公約数について，次のことが成立する．

割り算と最大公約数

２つの自然数\(a,\ b\ \) について，\( a\ \) を\( b\ \) で割ったときの商を\( q\) ，余りを\( r\ \) とすると

\( a\ \) と\( b\ \) の最大公約数は，\( b\ \) と\( r\ \) の最大公約数に等しい

証明）条件から，\( a\) を\( b\) で割ったときの商を\( q\)とすると，次の等式が成立する．

\( a=bq + r\cdots ①\)

①より

\( r=a-bq\cdots ②\)

\( a\)と\( b\)の最大公約数を\( a\)，\( b\)と\( r\)の最大公約数を\( n\)とする．

［1］

［2］

上のような最大公約数の求め方をユークリッドの互除法または単に互除法といいます。

ここでは，ユークリッドの互除法を使って\( △x + ⬜︎y=○\)の形の方程式を求めていきます。