5分でわかる!ユークリッドの互除法
![高校数学A](http://assets.try-it.jp/assets/modules/utilities/subject_symbol_border_k0_mathematics_a-105acb0eb8e2c91e69431967298e2e1f961eff61240840fcf27166ef295c9887.png)
- ポイント
- 例題
- 練習
![](http://assets.try-it.jp/assets/modules/components/movie_size-f89110ba4a351d85c483bb12f73c7cf89e2ba13a9174f58b4a38599d28678843.png)
この動画の要点まとめ
ポイント
最大公約数がわかる公式
![lecturer_avatar](https://d12rf6ppj1532r.cloudfront.net/imagawa.png)
そこで、素因数分解をしなくても2つの数の最大公約数がわかる法則 「ユークリッドの互除法」 について学習しよう。
![高校数学A 整数の性質26 ポイント](https://d12rf6ppj1532r.cloudfront.net/images/k/0/mat_a/2_2_26_1/k_mat_a_2_2_26_1_image01.png)
![lecturer_avatar](https://d12rf6ppj1532r.cloudfront.net/imagawa.png)
整数Aを整数Bで割ったとき、 「A=B×(商)+(余り)」 と表すことができるよね。このときの 「商」 を q 、 「余り」 を r とおくと、 「A=Bq+r」 と書き表すことができる。このとき、 「AとB」の最大公約数は、「Bとr」の最大公約数と等しくなる んだ。
![lecturer_avatar](https://d12rf6ppj1532r.cloudfront.net/imagawa.png)
ユークリッドの互除法を使えば、 「722と171の最大公約数は?」 などのように 大きい数の最大公約数 をたずねられても、最大公約数を簡単に求められるよ。具体的な互除法の使い方を、次のページで確認しよう。
【補足】ユークリッドの互除法が成り立つことの証明
![lecturer_avatar](https://d12rf6ppj1532r.cloudfront.net/imagawa.png)
ユークリッドの互除法が、なぜ成り立つのか気になる人もいるよね。証明は少し難しいんだけど、余裕がある人は、次の証明の手順についても流れをつかんでおこう。
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の最大公約数に等しい。
![](http://assets.try-it.jp/assets/modules/utilities/logo_black-a711ae7f4c2af1410b916e7066a5e8950d6f2f3a2150e093b6dc878ad8f31d3f.png)
ある2つの数の最大公約数を求めるとき、これまではそれぞれの数を素因数分解して求めてきたね。でも、例えば 「722と171の最大公約数は?」 などのように 大きい数の最大公約数 をたずねられると、それぞれの数を素因数分解するのはちょっと骨が折れそうだ。