5分でわかる！ユークリッドの互除法
- ポイント
- 例題
- 練習
子どもの勉強から大人の学び直しまで
ハイクオリティーな授業が見放題
この動画の要点まとめ
ポイント
最大公約数がわかる公式
そこで、素因数分解をしなくても2つの数の最大公約数がわかる法則 「ユークリッドの互除法」 について学習しよう。
整数Aを整数Bで割ったとき、 「A＝B×(商)+(余り)」 と表すことができるよね。このときの 「商」 を q 、 「余り」 を r とおくと、 「A＝Bq+r」 と書き表すことができる。このとき、 「AとB」の最大公約数は、「Bとr」の最大公約数と等しくなる んだ。
ユークリッドの互除法を使えば、 「722と171の最大公約数は？」 などのように 大きい数の最大公約数 をたずねられても、最大公約数を簡単に求められるよ。具体的な互除法の使い方を、次のページで確認しよう。
【補足】ユークリッドの互除法が成り立つことの証明
ユークリッドの互除法が、なぜ成り立つのか気になる人もいるよね。証明は少し難しいんだけど、余裕がある人は、次の証明の手順についても流れをつかんでおこう。
2つの正の整数A，B（A＞B）について，AをBで割ったときの商をq，余りをr，最大公約数をgとするとき，互いに素な自然数a'，b'（a'＞b'）を用いて，
A=ga'，B=gb'
と表すことができる。
このとき，
A-B=g(a'-b')
より，A，B，A-Bは，gを公約数にもつ。
また，「a'，b'が互いに素であれば、a'（またはb'）とa'-b'も互いに素である」という性質から，
AとBの最大公約数は，A-BとBの最大公約数に等しい。……①
①を繰り返し用いると，
A-BとBの最大公約数は，A-2BとBの最大公約数に等しい。
A-2BとBの最大公約数は，A-3BとBの最大公約数に等しい。
・
・
・
A-(q-1)BとBの最大公約数は，A-qBとBの最大公約数に等しい。
つまり，
AとBの最大公約数は，A-qBとBの最大公約数に等しい。……②
が成り立つ。
ここで，A，Bについて商と余りの関係から，
A=Bq+r
⇔ A-qB=r ……③
②，③から，
AとBの最大公約数は，Bとrの最大公約数に等しい。
ある2つの数の最大公約数を求めるとき、これまではそれぞれの数を素因数分解して求めてきたね。でも、例えば 「722と171の最大公約数は？」 などのように 大きい数の最大公約数 をたずねられると、それぞれの数を素因数分解するのはちょっと骨が折れそうだ。