【高校数A】整数の性質「ユークリッドの互除法」を元数学科が解説

今回は最大公約数を求める方法を伝授します！

 

いうて素因数分解を使えば解けるっちゃ解けるのですが、今回は別解をご紹介(● ˃̶͈̀ロ˂̶͈́)੭ꠥ⁾⁾

 

それが

ユークリッドの互除法

です！！！

 

 

ユークリッドの互除法とは？

 

次の性質を利用する方法です。

《証明》

aとbの最大公約数をm、bとrの最大公約数をnと置く。

mについて

まず$a=bq+r$を移項して

$r=a-bq$

mはaとbの最大公約数、つまりaとbの公約数なので、適当な整数a’、b’を用いて

$a=a^{\prime }m$
$b=b^{\prime }m$

と表せますね？これを先ほどの式に代入すると

$r=a^{\prime }m-b^{\prime }mq=m(a^{\prime }-b^{\prime }q)$

つまりmはrの約数ということです。

 

mはa、bの最大公約数であるためbの約数。

つまりmはbとrの公約数であるということ。

ここで思い出して欲しいのはnについて、nはbとrの最大公約数でしたね？

ということは

$m\leqq n$…①

nについて

nはbとrの公約数なので適当な整数b”、r”を用いて

$b=b”n$
$r=r”n$

と置けます。これを$a=bq+r$に代入すると

$a=b”nq+r”n=n(b”q+r”)$

よってnはaの約数。

またnはbとrの最大公約数であるためbの約数でもあるということ。

つまりnはaとbの公約数です。

 

mはaとbの最大公約数であるので$m\geqq n$…②

①②より$m=n$

したがってaとbの最大公約数はbとrの最大公約数と等しい。《証明終わり》

 

この性質を利用した最大公約数の求め方をユークリッドの互除法と言います。

 

互除法を使って問題を解いてみよう。

 

割り切れた時の割った数が最大公約数になります。したがって答えは59。

 

最後に

ユークリッドさんすごいですね！『ジルの互除法』狙っていこうかな？ww