おいしい数学HOMEへのリンク

ユークリッドの互除法による最大公約数の求め方

整数(教科書範囲) ★★


アイキャッチ

ユークリッドの互除法のイメージと理論的な概念,ユークリッドの互除法を使って最大公約数を求める方法を説明します.



ユークリッドの互除法のイメージ

例題

例題

縦 $345 \rm{cm}$ ,横 $506 \rm{cm}$ の長方形の部屋を敷き並べることができる正方形のタイルの最大の一辺の長さを求めよ.


この答えが, $345$ と $506$ の最大公約数であることは容易です.

しかし,$345$ と $506$ は数が大きいので普通に計算すると少々大変です.

ユークリッドの互除法のイメージ

ユークリッドの互除法の導入

部屋を書きました.

最大公約数を求めるために,長方形内の最大の正方形を作り,余った長方形を考えます.

ユークリッドの互除法の導入2

余った長方形を敷き並べることができる正方形のタイルで,左の正方形も並べることができるので,

( $\boldsymbol{506}$ と $\boldsymbol{345}$ の最大公約数)

$\boldsymbol{=}$ ( $\boldsymbol{345}$ と $\boldsymbol{161}$ の最大公約数) 

が言えます.これを互除法の原理と言います.

互除法の原理を繰り返せば,数字が小さくなって,最大公約数を見つけやすいはずです.先ほどの右の長方形に同じことを繰り返し適用します.

ユークリッドの互除法の導入3
ユークリッドの互除法の導入4

つまり

( $506$ と $345$ の最大公約数)

$=$ ( $345$ と $161$ の最大公約数) 

$=$ ( $161$ と $23$ の最大公約数) $=23$

こうして最大公約数を求めることができました.答えは $\boldsymbol{23 \ \rm cm}$ です.

こうして互除法の原理を繰り返して最大公約数を求める手法をユークリッドの互除法といいます.

互除法の原理

ポイント

互除法の原理

自然数 $a$ を 自然数 $b$ で割ったときの余りを $r$ とすると

$\gcd (a,b)=\gcd (b,r)$

ただし,$\gcd (a,b)$ は $a$ と $b$ の最大公約数を表す.

互除法の原理の証明

証明

$a$ を $b$ で割ったときの商を $q$,$c=\gcd (a,b)$,$d=\gcd (b,r)$,$a=ca'$,$b=cb'$ とすると

$a=bq+r$

$\Longleftrightarrow r=a-bq$

$\Longleftrightarrow r=c(a'-b'q)$

より $c$ は $r$ の約数.$c$ は $b$ の約数でもあるので,$c$ は $b$ と $r$ の公約数である.

$\therefore \ c \leqq d \ \ \cdots$ ①

また,$b=db''$,$r=dr'$ とすると

$a=bq+r$

$\Longleftrightarrow a=d(b''q+r')$

より $d$ は $a$ の約数.$d$ は $b$ の約数でもあるので,$d$ は $a$ と $b$ の公約数である.

$\therefore \ d \leqq c \ \ \cdots$ ②

①,②より $c=d$

※ この証明は例えば2019年順天堂大学医学部で出題されています.


ユークリッドの互除法による最大公約数の求め方(例題と練習問題)

例題

例題

$345$ と $506$ の最大公約数を求めよ.


講義

上の例題の数字を再度使います.大きい数 $\div$ 小さい数をして,再利用するように書いていきます.


解答と解説

普通に割り算をします.書くときになるべく右に書くようにします.


ユークリッドの互除法による最大公約数の求め方の計算法

$345$ を今出てきた余りである $161$ で割ります.


ユークリッドの互除法による最大公約数の求め方の計算法2

同様に $161$ を今出てきた余りである $23$ で割ります.

ユークリッドの互除法による最大公約数の求め方の計算法3

余りが $0$ になったら終わりで,1番左に書いてある数字(最後に割る数)が答えになります.

$\therefore \ \gcd (345,506)=\boldsymbol{23}$

練習問題

練習

(1) $310$ と $837$ の最大公約数を求めよ.

(2) $629$ と $459$ の最大公約数を求めよ.

練習の解答

(1)

ユークリッドの互除法による最大公約数の求め方の計算法練習1

$\therefore \ \gcd (310,837)=\boldsymbol{31}$


(2)

ユークリッドの互除法による最大公約数の求め方の計算法練習2

$\therefore \ \gcd (629,459)=\boldsymbol{17}$