おいしい数学ホームへのリンク

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

タイプ:教科書範囲 レベル:★★ 


アイキャッチ

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





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

例題

例題

縦 $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$ の最大公約数を表す.

互除法の原理の証明





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

上の例題の数字を再度使います.


例題

例題

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


講義

大きい数 $\div$ 小さい数をして,再利用するように書いていきます.


解答と解説

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


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

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


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

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

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

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

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



練習問題

練習1

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

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

練習の解答



ノートに戻る