|
Apendix 2 ユークリッドの互除法 | |
| f-denshi.com 最終更新日： *** | ||
| ［目次へ］ | ||
［１］ 最大公約数の定義です。
整数 a、d があたえられて、
a＝d・q となるような整数q が存在するとき、d を a の約数、あるいは a は d の倍数であるといいます。 b＝d・q’ となるq’が存在するとき、d は a と b の公約数であるといいます。 （a、b） と書きます。 |
［１］ 最大公約数を求めるアルゴリズムは以下のとおりです。
| ユークリッドの互除法
正整数a、b（a＞b）が与えられたとき、以下の方法で最大公約数が求められる。 ［第０ステップ］ ［第１ステップ］ ・・・・・・・・・・・・・・・・・・ ［第ｋステップ］ これを繰り返すと、ｒ0＞ｒ１・・＞ｒk・・・＞0 なので、いつか必ず、 ［第ｎステップ］ となる。このとき、ｒn は a と b の最大公約数である。すなわち、 （a、b）＝ｒn である。 |
［２］ 証明は次の命題を繰り返し用いて行います。
| 命題
正整数a、b（a＞b）が与えられたとき、aをbで割った商をq、余りをｒとする。すなわち、 a＝qb＋ｒ （０≦ｒ＜b） （a、b）＝（b、ｒ）
|
証明
a＝qb＋ｒ (1)
r＝a－qb (2)
(a，b)＝m， (b，r)＝n とします。
(1)より，右辺はnで割り切れるので，左辺aもnで割り切れる。
⇒ nはaとbの公約数で，n≦m
(2)より，右辺はmで割り切れるので，左辺rもmでわり切れる。
⇒ mはrとbの公約数で，m≦n
したがって，m＝nであることが分かります。
［３］ この命題をユークリッドの互除法の第０ステップに適用すれば、
（a、b）＝（ｒ0、ｒ1）
第１ステップ、・・・、第ｎ－１ステップと順に適用すれば、
（ｒ0、ｒ1）＝（ｒ1、ｒ2）＝・・・＝（ｒn-1、ｒn）＝ｒn
がわかります。すなわち、
（a、b）＝ｒn
であることがわかります。
［４］ ユークリッドの互除法のプロセスを逆に辿ると、非常に重要な次の定理を得ます。
| 定理
整数 a、b が与えられ、a と b の最大公約数を d とする。このとき、 Xa＋Yb＝d をみたす整数 X、Y が存在する。 |
（証明）
ユークリッドの互除法で第０から第（ｎ－１）ステップ [#] までを変形すると
ｒ1＝a＋q1b
↓
ｒ2＝b＋q2ｒ1
↓
ｒ3 ｒ1＋q3ｒ2
・・・・・・・・
ｒn-1＝ｒn-3＋qn-1ｒn-2
↓
ｒn＝ｒn-2＋qnｒn-1
となりますが、各式の右辺を下の式に↓順に代入してｒ1、ｒ2、・・・ｒn-1を消去していくと、
ｒ2 ＝b＋q2（a＋q1b）
ｒ3 ＝（a＋q1b）＋q3（b＋q2（a＋q1b））
＝（1＋q2q3）a＋（q1＋q1q2＋q3）b
・・・・・・・・
↓
ｒn ＝（qi の積と和）×a＋（qi の積と和）×b
を得ます。ここで，qi の積と和はもちろん整数ですから定理が証明されたことになります。
以上の考察は多項式に置き換えてもそのまま成り立ちます。⇒ 定理
［５］ 具体的に見てみましょう。定理によると、a＝182、b＝21 が与えられると
最大公約数 d＝7 ⇒ 182X＋21Y＝7 となる整数 X、Y が存在する
が成り立ちます。ユークリッドの互除法で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・14
＝21－1・（182－8・21）
＝-1・182＋9・21
すなわち、X＝-1、Y＝9 が方程式 182X＋21Y＝7 解の一組として求まります。
このプロセスは辺の長さが182×21の長方形を埋め尽くす正方形のうちで、一辺の長さが最大のものを求めるアルゴリズムと同じになっています。右の図を参照に考察してください。