高校数学A

高校数学A
5分でわかる!ユークリッドの互除法

313

5分でわかる!ユークリッドの互除法

313
学年別フルラインナップキャンペーン学年別フルラインナップキャンペーン

この動画の要点まとめ

ポイント

ユークリッドの互除法

高校数学A 整数の性質26 ポイント

これでわかる!
ポイントの解説授業
lecturer_avatar

ある2つの数の最大公約数を求めるとき、これまではそれぞれの数を素因数分解して求めてきたね。でも、例えば 「722と171の最大公約数は?」 などのように 大きい数の最大公約数 をたずねられると、それぞれの数を素因数分解するのはちょっと骨が折れそうだ。

最大公約数がわかる公式

lecturer_avatar

そこで、素因数分解をしなくても2つの数の最大公約数がわかる法則 「ユークリッドの互除法」 について学習しよう。

POINT
高校数学A 整数の性質26 ポイント
lecturer_avatar

整数Aを整数Bで割ったとき、 「A=B×(商)+(余り)」 と表すことができるよね。このときの 「商」q「余り」r とおくと、 「A=Bq+r」 と書き表すことができる。このとき、 「AとB」の最大公約数は、「Bとr」の最大公約数と等しくなる んだ。

lecturer_avatar

ユークリッドの互除法を使えば、 「722と171の最大公約数は?」 などのように 大きい数の最大公約数 をたずねられても、最大公約数を簡単に求められるよ。具体的な互除法の使い方を、次のページで確認しよう。

【補足】ユークリッドの互除法が成り立つことの証明

lecturer_avatar

ユークリッドの互除法が、なぜ成り立つのか気になる人もいるよね。証明は少し難しいんだけど、余裕がある人は、次の証明の手順についても流れをつかんでおこう。

ユークリッドの互除法の証明

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の最大公約数に等しい。

この授業の先生

今川 和哉 先生

どんなに数学がニガテな生徒でも「これだけ身につければ解ける」という超重要ポイントを、 中学生が覚えやすいフレーズとビジュアルで整理。難解に思える高校数学も、優しく丁寧な語り口で指導。

学年別フルラインナップキャンペーン
ユークリッドの互除法
313
友達にシェアしよう!
学年別フルラインナップキャンペーン