Ｅｕｃｌｉｄの互除法
数学セミナー（２００２年６月号）で、「因数分解のひろがり」を主テーマに特集が組まれた。
いろいろな話題が取り上げられ、楽しく拝読することができた。その中で、ユークリッドの互
除法について、特に関心をもったので、ここで整理しておきたい。
ユークリッドは、古代アレキサンドリアの数学者である。ユークリッドの互除法は、共通因
数を求める最速のアルゴリズムとして、現代において暗号理論（公開鍵方式）などに多用さ
れており、ユークリッドの偉大さに、ただ敬服するばかりである。
ここで、少しばかり予備知識を確認しておきたい。以下で数はすべて０以上の整数とする。
数 ａ、ｂ（ｂは０でない）に対して、
ａ＝ｂＱ＋Ｒ （０≦Ｒ＜ｂ）
となる数Ｑ、Ｒがただ一つ存在する。
特に、Ｒ＝０ のとき、即ち、
数 ａ、ｂ（ｂは０でない）に対して、ａ＝ｂＱ となる数 Ｑ が存在するとき、
ａ は ｂで割り切れる、ａ はｂの倍数、ｂ はａの約数、．．．
という。
ａ、ｂ、．．．に共通な倍数を公倍数といい、その中で最小なものを最小公倍数（L．C．M．)
ａ、ｂ、．．．に共通な約数を公約数といい、その中で最大なものを最大公約数（Ｇ．C．M．)
という。
このとき、公倍数は、最小公倍数の倍数、公約数は、最大公約数の約数 である。
特に、ａ、ｂの最大公約数を、(ａ，ｂ) という記号で表す。
数 ａ、ｂに対して、最大公約数を Ｇ、最小公倍数を Ｌ とする。次の事実は基本的である。
定理 （A，Ｂ）＝１である数A、Ｂを用いて、ａ＝AＧ、ｂ＝ＢＧ と書ける。
また、ａｂ＝ＧＬ が成り立つ。
定理 （ａ，ｂ）＝１で、ｂｃ が ａ で割り切れるならば、ｃ は ａ で割り切れる。
（証明） （ａ，ｂ）＝１より、ａｂ＝Ｌ が成り立つ。ｂｃ が ａ の倍数なので、ｂｃ
は ａ、ｂ の公倍
数となる。よって、ｂｃ はＬ（＝ａｂ）の倍数となり、ｂｃ は ａｂ
で割り切れる。
従って、ｃ は ａ で割り切れる。 （証終）
次の定理は、ユークリッドの互除法の理論的根拠を与える。
定理 （ａ，ｂ）＝（ａ−ｂＱ，ｂ）
（証明） Ｇ＝（ａ，ｂ）より、Ｇ は ａ、ｂ の約数なので、ａ−ｂＱ の約数でもある。
よって、Ｇ は、ａ−ｂＱ、ｂ の公約数となり、Ｇ は、（ａ−ｂＱ，ｂ）
の約数となる。
逆に、ａ−ｂＱ＝Ｘ とおくと、ａ＝Ｘ＋ｂＱ なので、（Ｘ，ｂ） は
ａ の約数となる。
よって、（Ｘ，ｂ） は ａ、ｂ の公約数となり、（ａ−ｂＱ，ｂ） は、Ｇ
の約数となる。
従って、（ａ，ｂ）＝（ａ−ｂＱ，ｂ） が成り立つ。 （証終）
ユークリッドの互除法
（ａ，ｂ）＝（ｂ，ｃ）＝（ｃ，ｄ）＝・・・＝（ｅ，ｆ）＝ｆ
ｃはａをｂで割った余り
ｄはｂをｃで割った余り
・・・・・・・
ｅをｆで割った余りが０
例 ２９５２ と １３６８ の最大公約数を、ユークリッドの互除法を用いて求めてみよう。
２９５２＝１３６８×２＋２１６
１３６８＝２１６×６＋７２
２１６＝７２×３＋０ 従って、最大公約数は、７２ となる。
私が中学生の頃、次のような筆算形式で最大公約数を求めたことを覚えている。
この計算も、ユークリッドの互除法の一変化である。
 |
左の計算から、求める最大公約数は、７２ である。 もちろん、左の計算とは別に、２つの数を割り切る素数を使って、どんどん 割っていき、割れなくなるまでの素数の積を求めれば、それが、最大公約 数となる。（多くの方は、多分こちらの計算方法のほうをご存知でしょう。） |
上記の互除法の計算は、教科書的であるが、次のように計算する方法もある。
互除法の原理を説明するとき、昔だったら上記のような計算で示したが、最近の高校の
教科書では、視覚的に訴える意味で図を用いる場合が多いようだ。
例 ３２と１４の最大公約数を求めよ。
下図のように、横の長さが３２、縦の長さが１４の長方形を考え、１辺の長さが同一の正
方形で埋め尽くす。そのときの正方形の最大辺の長さが最大公約数を与える。
上図をにらめっこしていると、
３２＝１４×２＋４
１４＝４×３＋２
４＝２×２＋０ よって、 最大公約数は、２
という計算の意味づけが目に浮かんでくるようだ。
最大公約数を求めることで、他にもいろいろな応用例が考えられる。
| （応用例１）・・・分数 |  |
の約分（分子・分母を割り切る数が不明なときに有効！） |
ユークリッドの互除法により、２９５２＝４１×７２、１３６８＝１９×７２ とかけるので
| 求める既約分数は、 |  |
上記の分数の約分では、ユークリッドの互除法のご利益を余り感じないかもしれない。
| 次の分数 |  |
の約分はどうであろうか？一見すると、既約分数のような気がするが、 |
| 実は約分されて、 |  |
となる。この場合、分子・分母の共通因数を見つけること自体難 |
| しいし、もしかしたら、約分しようと考えないかもしれない。ユークリッドの互除法を知って | ||
| いれば、簡単に共通因数を見つけることができる。 | ||
（応用例２）・・・不定方程式の解法（解の一つが簡単に求められます！）
２９５２と１３６８の最大公約数を求める式を上手く式変形すると、不定方程式の解を得
ることができる。
７２＝１３６８−２１６×６
＝１３６８−（２９５２−１３６８×２）×６
＝１３６８×１３＋２９５２×（−６）
以上から、不定方程式 １３６８Ｘ＋２９５２Ｙ＝７２の解の一つとして、Ｘ＝１３、Ｙ＝−６を
得る。不定方程式は、解が一つ見つかれば、全ての解は簡単に求められる。
また、不定方程式の特殊解を筆算形式で求める方法が知られている。
（→ 参考：特別講義 ２次体の整数論の「不定方程式」）
不定方程式というと、「解は無数！」という雰囲気があるが、平成２０年度の灘中学の入
試問題は、奇跡の１題で、神のなせる技のような趣である。
１個６６円の柿と１個３５円のミカンを合わせて３８９０円分買った。このとき、柿と
ミカンはそれぞれ何個ずつ買ったのか？
（解） 柿を ｘ 個、ミカンを ｙ 個買ったものとすると、 ６６ｘ＋３５ｙ＝３８９０
６６＝３５×１＋３１ より、 ３１＝６６−３５
３５＝３１×１＋４ より、 ４＝３５−３１＝３５×２−６６
３１＝４×７＋３ より、 ３＝６６−３５−（３５×２−６６）×７＝６６×８−３５×１５
４＝３×１＋１ より、 ３５×２−６６−６６×８＋３５×１５＝１
すなわち、 ６６×（−９）＋３５×１７＝１
よって、 ６６×（−３５０１０）＋３５×６６１３０＝３８９０ より、
６６（ｘ＋３５０１０）＋３５（ｙ−６６１３０）＝０
このとき、 整数 ｔ に対して、 ｘ＝３５ｔ−３５０１０ 、 ｙ＝６６１３０−６６ｔ
ｘ 、 ｙ は０以上の整数なので、 ３５ｔ−３５０１０≧０ 、 ６６１３０−６６ｔ≧０
これを解いて、 １０００．２＜ｔ＜１００１．９７ より、 ｔ＝１００１
このとき、 ｘ＝２５ 、 ｙ＝６４ である。 （終）
（コメント） 解答を書いていて、疑問に思ったことがある。「この問題は、小学生が解くんだ
よな〜？」 でも、灘中を受験する小学生なら、「まっ、いいか！」という感じかな？
純粋な小学生対象に、どのように解答すべきなのか、悩むところだ。上記の計算を省みて
次のように考えることもできるが、これが小学生向きかな？
（別解） ６６ｘ＋３５ｙ＝３８９０ において、ｘ は５の倍数、ｙ は２の倍数である。
（当ＨＰ読者のＨＮ「yuki」さんからも、このような視点のアドバイスをメールでいただいた。
（平成２６年６月１３日付け））
よって、 ｘ＝５ａ 、 ｙ＝２ｂ とおいて代入すると、 ３３ａ＋７ｂ＝３８９
７ｂ＝３８９−３３ａ≧０ より、 ０≦ａ≦１１
ａ＝０ のとき、 ７ｂ＝３８９ （不適）
ａ＝１ のとき、 ７ｂ＝３８９−３３＝３５６ （不適）
ａ＝２ のとき、 ７ｂ＝３８９−６６＝３２３ （不適）
ａ＝３ のとき、 ７ｂ＝３８９−９９＝２９０ （不適）
ａ＝４ のとき、 ７ｂ＝３８９−１３２＝２５７ （不適）
ａ＝５ のとき、 ７ｂ＝３８９−１６５＝２２４ より、 ｂ＝３２
ａ＝６ のとき、 ７ｂ＝３８９−１９８＝１９１ （不適）
ａ＝７ のとき、 ７ｂ＝３８９−２３１＝１５８ （不適）
ａ＝８ のとき、 ７ｂ＝３８９−２６４＝１２５ （不適）
ａ＝９ のとき、 ７ｂ＝３８９−２９７＝９２ （不適）
ａ＝１０ のとき、 ７ｂ＝３８９−３３０＝５９ （不適）
ａ＝１１ のとき、 ７ｂ＝３８９−３６３＝２６ （不適）
以上から、求める解は、
ａ＝５ 、 ｂ＝３２ より、 ｘ＝２５ 、 ｂ＝６４ （終）
当ＨＰがいつもお世話になっているＨＮ「攻略法」さんから小学生向けの解答を始めいろい
ろな解答をお寄せいただいた。（平成２２年１０月１９日付け）
■鶴亀算として考える
（解） すべて柿とすると、 ３８９０÷６６＝５８・・・６２ なので、いくつかはミカンである。
３８９０＝６６×５８＋６２＝６６×５７＋１２８＝６６×５７＋３５×２＋５８
１個の柿を２個のミカンと交換すると、余りが ６２−５８＝４ だけ減る。
ここで、１２８は４の倍数なので、上記の計算を、次のように変形する。
３８９０＝６６×５７＋１２８＝６６×５７＋（３５×２−６６×１）×３２＝６６×２５＋３５×６４
よって、 柿を ２５個 と ミカンを ６４個 買えばよい。 （終）
（別解） すべてミカンとすると、 ３８９０＝３５×１１１＋５ なので、いくつかは柿である。
３８９０＝３５×１１１＋５＝３５×１１４−１００＝３５×１１４−（３５×２−６６×１）×２５
より、 ３８９０＝３５×６４＋６６×２５
よって、 柿を ２５個 と ミカンを ６４個 買えばよい。 （終）
■合同式で考える
（解） 柿を
ｘ 個、ミカンを ｙ 個買うとすると、
「不定方程式 ６６ｘ＋３５ｙ＝３８９０ の非負の整数解( ｘ ，ｙ
)」を求めればよい。
６６ｘ≡３８９０ （ｍｏｄ ３５） または ３５ｙ≡３８９０ （ｍｏｄ ６６）を考えればよい。
６６ｘ≡３８９０ （ｍｏｄ ３５） の場合
６６≡３１ （ｍｏｄ ３５） 、３８９０≡５ （ｍｏｄ ３５） となるので、
３１ｘ≡５ （ｍｏｄ ３５）
３５ｘ≡３５ （ｍｏｄ ３５） を辺々引いて、 ４ｘ≡３０ （ｍｏｄ ３５）
両辺を８倍して、 ３２ｘ≡２４０ （ｍｏｄ ３５） より、 ３２ｘ≡３０ （ｍｏｄ ３５）
３１ｘ≡５ （ｍｏｄ ３５） を辺々引いて、 ｘ≡２５ （ｍｏｄ ３５）
よって、 ｘ＝３５ｎ＋２５ （ｎ
は整数）と書ける。
このとき、 ３５ｙ＝３８９０−６６ｘ＝３８９０−６６（３５ｎ＋２５）＝２２４０−２３１０ｎ より、
ｙ＝６４−６６ｎ≧０ より、 ｎ≦３２/３３
また、 ｘ＝３５ｎ＋２５≧０ より、 ｎ≧−５/７ より、 −５/７≦ｎ≦３２/３３
ｎ
は整数なので、 ｎ＝０ となる。よって、 ｘ＝２５ 、ｙ＝６４
したがって、 柿を ２５個 と ミカンを ６４個 買えばよい。 （終）
■剰余類の表を作成する（計算機向き） （→ 参考：「線形結合の問題」）
（解） ３８９０＝６６×５８＋６２ より、６６を法とする剰余類は、
６２
６２＋１×６６＝１２８
６２＋２×６６＝１９４
６２＋３×６６＝２６０
・・・・・・・・・・・・
６２＋３３×６６＝２２４０＝６４×３５ ←
３５の倍数
・・・・・・・・・・・・
６２＋５８×６６＝３８９０
よって、ミカンは、６４個、柿は、(３８９０−６４×３５)/６６＝２５個 （終）
一般的に記述すると、ａ
を法とする剰余類は、
(ｃ ｍｏｄ ａ)
(ｃ ｍｏｄ ａ)＋１×ａ
(ｃ ｍｏｄ ａ)＋２×ａ
(ｃ ｍｏｄ
ａ)＋３×ａ
・・・・・・・・・・・・
(ｃ ｍｏｄ ａ)＋ｋ×ａ＝Ｙｋ×ｂ ← ｂ
の倍数なら、(ｘ，ｙ)=((ｃ−Ｙｋ×ｂ)/ａ，Ｙｋ)
※複数個の場合もある
・・・・・・・・・・・・
(ｃ
ｍｏｄ ａ)＋ＩＮＴ（ｃ/ａ）×ａ
である。
（コメント） 攻略法さんに感謝します。
読者のために練習問題を作成してみました。（平成２９年６月２５日付け）
練習問題 １個７１円の柿と１個３２円のミカンを合わせて２０１７円分買った。このと
き、柿とミカンはそれぞれ何個ずつ買ったのか？
この問題を不定方程式として解くと次のようになるだろう。
（解） ７１ｘ＋３２ｙ＝２０１７ の一般解は、
ｘ＝３２ｋ−１８１５３ 、ｙ＝４０３４０−７１ｋ （ｋは整数）
ｘ＞０ 、ｙ＞０ より、 ５６７．２・・・＜ｋ＜５６８．１・・・・ なので、 ｋ＝５６８
よって、 ｘ＝２３ 、ｙ＝１２ （終）
上記の解答を見て造作ないように感じられるかもしれないが、相当途中の計算を省略して
いるので、結構大変である。
これに対して、攻略法さんの鶴亀算的解法をとれば、計算はぐっと楽になる。
（別解） ２０１７＝７１×２８＋２９＝７１×２７＋１００＝７１×２７＋４×２５ で、
２５＝３２×３−７１ なので、 ２０１７＝７１×２３＋３２×１２
よって、柿は、２３個、ミカンは、１２個ずつ買える。 （終）
練習問題をもう一つ。
練習問題 １１０円の大きいジュースと７０円の小さいジュースを何個かずつ買ったら
代金が１３７０円になった。このとき、大小それぞれ何個ずつ買ったか。
（解） １３７０＝１１０×１２＋５０＝１１０×８＋４９０＝１１０×８＋７０×７
これより、大は８個、小は７個買った。 （終）
（別解） １３７０÷（１１０＋７０）＝７ 余り １１０
よって、大は８個、小は７個買った。 （終）
（コメント） この手の解法を見ると、不定方程式の一般的解法が虚しく思える。
ユークリッドの互除法を用いて、最大公約数を求める場合、いったい何回ぐらい割り算を
実行すればよいのかが気にかかる。これについては、次の書籍に詳しい記述がある。
和田秀男 著 数の世界 整数論への道（岩波書店）
上記書籍によれば、割り算の回数 ｎ を固定したときの、最初に割られる数
ａ の最小値
を求めることは、フィボナッチ数列 １，１，２，３，５，８，１３，２１，３４，・・・と関係していて、
ｎ＝１９ のとき、ａ＝１０９４６ だという。つまり、１００００より小さい数と、さらにそれより小
さい何がしかの数との最大公約数を求める場合、最大１８回の割り算が必要とのことであ
る。
また、回数の計算について、次の定理が知られている。
ラメの定理 ｎ≦４．７９×（ａの桁数）−０．３７
ａが４桁の数とすると、ｎ≦１８．７９ で上記結果と同じである。
このラメの定理のおかげで、ユークリッドの互除法を用いて最大公約数を求める場合、
ある程度の計算に対する心構えを持つことができるのではないだろうか。
（追記） 令和２年１０月１０日付け
「１６４９と１８４３の最大公約数を求めよ」と問われれば、真っ先に互除法を用いて、
１８４３÷１６４９＝１・・・１９４
１６４９÷１９４＝８・・・９７
１９４÷９７＝２・・・０ から、最大公約数は、９７
とするだろう。ただし、最大公約数が１でない（すなわち、互いに素でない）ことが分かってい
れば、次のようにして簡単に最大公約数が求められる。
１８４３−１６４９＝１９４ も最大公約数の倍数である。
１９４＝２×９７ で、 １８４３÷９７＝１９・・・０ 、１６４９÷９７＝１７・・・０ から、
１８４３、１６４９ともに、９７で割り切れ、１９４では割り切れない。
よって、最大公約数は、９７である。
（参考文献：数学セミナー（２００２年６月号）特集「因数分解のひろがり」
高木貞治 著 初等整数論講義（岩波書店）
和田秀男 著 数の世界 整数論への道（岩波書店）
小島寛之 著 数学の遺伝子（日本実業出版社））