Apendix 2　ユークリッドの互除法
f-denshi.com  最終更新日： ***

１．最大公約数の定義

［１］　最大公約数の定義です。

整数　ａ、ｄ　があたえられて、
ａ＝ｄ・ｑ

となるような整数ｑ　が存在するとき、ｄ を ａ の約数、あるいは ａ は ｄ の倍数であるといいます。
さらに、整数 ｂ があたえられ、ｄ が ｂ の約数でもあるとき、すなわち、

ｂ＝ｄ・ｑ’

となるｑ’が存在するとき、ｄ は ａ と ｂ の公約数であるといいます。
また、ａ、ｂ の公約数のうちで最大のものを最大公約数といい、

（ａ、ｂ）

と書きます。

２．ユークリッドの互除法

［１］　最大公約数を求めるアルゴリズムは以下のとおりです。

ユークリッドの互除法

正整数ａ、ｂ（ａ＞ｂ）が与えられたとき、以下の方法で最大公約数が求められる。
　（ただし、ｂ＝ｒ0と記し、各ステップの割り算の商を正の整数、ｑ1、ｑ2、・・・、ｑn+1　とした）

［第０ステップ］　
　　　　ａをｒ0（＝ｂ）で割り、
　　　　　　　　　　　　　ａ＝ｑ1ｒ0＋ｒ1　　　　（０＜ｒ１＜ｒ0）
　　とする。

［第１ステップ］　
　　　　ｒ0をｒ1で割り、
　　　　　　　　　　　　　ｒ0＝ｑ2ｒ1＋ｒ2　　　　（０＜ｒ2＜ｒ1）
　　とする。　　　

　　　　・・・・・・・・・・・・・・・・・・

［第ｋステップ］　
　　　　ｒk-1をｒkで割り、
　　　　　　　　　　　　　ｒk-1＝ｑk+1ｒk＋ｒk+1　（０＜ｒk+1＜ｒk）
　　とする。

　　これを繰り返すと、ｒ0＞ｒ１・・＞ｒk・・・＞0　なので、いつか必ず、

［第ｎステップ］　
　　　　ｒn-1はｒnで割りきれ、
　　　　　　　　　　　　　ｒn-1＝ｑn+1ｒn　　　　　　　

　　となる。このとき、ｒnはaとbの最大公約数である。すなわち、

　　　　（ａ、ｂ）＝ｒn

　　である。

［２］　証明は次の命題を繰り返し用いて行います。　　　　　　　

命題　　　

正整数ａ、ｂ（ａ＞ｂ）が与えられたとき、ａをｂで割った商をｑ、余りをｒとする。すなわち、

　　　　　　ａ＝ｑｂ＋ｒ　　　（０≦ｒ＜ｂ）
とすると、

　　　　　　（ａ、ｂ）＝（ｂ、ｒ）　　　　　　

証明→[#]　　　　　　　　　　　　　

［３］　この命題をユークリッドの互除法の第０ステップに適用すれば、

（ａ、ｂ）＝（ｒ0、ｒ1）

第１ステップ、・・・、第ｎ－１ステップと順に適用すれば、

（ｒ0、ｒ1）＝（ｒ1、ｒ2）＝・・・＝（ｒn-1、ｒn）＝ｒn

がわかります。すなわち、

（ａ、ｂ）＝ｒn

であることがわかります。

［４］　ユークリッドの互除法のプロセスを逆に辿ると、非常に重要な次の定理を得ます。

定理

整数 ａ、ｂ が与えられ、ａ と ｂ の最大公約数を ｄ とする。このとき、

Ｘａ＋Ｙｂ＝ｄ

をみたす整数 Ｘ、Ｙ が存在する。

（証明）

ユークリッドの互除法で第０から第（ｎ－１）ステップまでを変形すると

ｒ1　＝a　　＋ｑ1b
ｒ2　＝b　　＋ｑ2ｒ1
ｒ3　＝ｒ1　 ＋ｑ3ｒ2
　　　　　・・・・・・・・
ｒn-1＝ｒn-3＋ｑn-1ｒn-2
ｒn　＝ｒn-2＋ｑnｒn-1　　　

となりますが、各右辺を下の式に順に代入してｒ1、ｒ2、・・・ｒn-1を消去していくと、

ｒ2　＝b　　＋ｑ2（a＋ｑ1b）
ｒ3　＝（a＋ｑ1b）＋ｑ3（b＋ｑ2（a＋ｑ1b））
　　＝（1＋ｑ2ｑ3）a＋（ｑ1＋ｑ1ｑ2＋ｑ3）b
　　　　　　・・・・・・・・
　　　　　↓
ｒn　＝（ｑi の積と和）a＋（ｑi の積と和）b

を得ます。ｑi の積と和はもちろん整数ですから定理が証明されたことになります。

［５］　具体的に見てみましょう。定理によると、a＝182、b＝21　が与えられると

最大公約数　ｄ＝7　⇒　　182Ｘ＋21Ｙ＝7　となる整数 Ｘ、Ｙ が存在する

が成り立ちます。ユークリッドの互除法で182と21の最大公約数を求める過程は、

182＝8・21＋14　　　 →　14＝182-8・21　　・・・①
　21＝1・14＋7　　　　→　 7＝21－1・14　　・・・②
　14＝2・7

となり、d＝７がわかります。さらに、①を②に代入して、

7＝21－1・（182－8・21）
　＝-1・182＋9・21

すなわち、Ｘ＝-1、Ｙ＝9　が解の一組として求まります。

　このプロセスは辺の長さが182×21の長方形を埋め尽くす正方形のうちで、一辺の長さが最大のものを求めるアルゴリズムと同じになっています。右の図を参照に考察してください。

命題の証明