みなさんおはこんばんにちは。
アヒージョを作ってみたいジルでございます！
今回は最大公約数を求める方法を伝授します！
いうて素因数分解を使えば解けるっちゃ解けるのですが、今回は別解をご紹介(● ˃̶͈̀ロ˂̶͈́)੭ꠥ⁾⁾
それが
ユークリッドの互除法
です！！！
ユークリッドの互除法とは？
次の性質を利用する方法です。
この性質を下で証明しました！
《証明》
aとbの最大公約数をm、bとrの最大公約数をnと置く。
mについて
まず$a=bq+r$を移項して
$r=a-bq$
mはaとbの最大公約数、つまりaとbの公約数なので、適当な整数a’、b’を用いて
$a=a’m$
$b=b’m$
と表せますね？これを先ほどの式に代入すると
$r=a’m-b’mq=m(a’-b’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
楽しい数学Lifeを！
