ユークリッド互除法と2元1次不定方程式！例題で分かりやすく理解

ユークリッドの互除法とは、2つの整数の最大公約数を求めるような方法です。
これを応用して、2元1次不定方程式の解を求めることもできます。

情報や数学の分野に「アルゴリズム」という言葉があります。
アルゴリズムとは、「問題を解くための手段」といった意味ですが、明示的に記述された最古のアルゴリズムとしても、ユークリッドの互除法が知られています。

この記事では、そんなユークリッド互除法について例題を出しながらまとめます。

１．「ユークリッドの互除法」って、そもそもユークリッドとは？

ユークリッド（Euclid）とは、アレクサンドリアのエウクレイデスを英語にしたものです。彼は古代ギリシャの人物で、今のエジプトあたりに住んでいました。

プトレマイオス1世の時代（紀元前323年～紀元前283年）に数学者、天文学者として大変活躍した人物であり、光学、透視図法、円錐曲線論、球面天文学などについても、研究をしていたと言われています。

プトレマイオス1世といえば、アレクサンドロス大王（アレクサンドロス3世）に仕え、プトレマイオス朝の初代ファラオですね。
古代エジプトの美女として有名な「クレオパトラ（クレオパトラ7世）」はプトレマイオス朝の最後のファラオです。

ガイウス・ユリウス・カエサルとの関係など、このまま歴史のお話をするのも面白いですが、数学に話を戻しましょう。

ユークリッドが著した『原論（ユークリッド原論）』は、数学史上最も有名な著作の一つです。
このことから、ユークリッドは「幾何学の父」とも呼ばれます。

音楽においてはバッハが「音楽の父」と呼ばれますが、ユークリッドは数学上、そのくらいの成果を上げた人物なのです。

数学上でユークリッドの名前を冠するようなものは非常に多く、ユークリッド幾何学やユークリッド空間、ユークリッド距離などがあります。

ユークリッド互除法は、「ユークリッド原論」の第7巻、命題1に記されていました。

２．ユークリッド互除法とは

ユークリッド原論には、「ユークリッドの互除法」について、以下のように記述されています。

以上のように、2数を割った余りを考えていくことで、最大公約数を求める方法が、ユークリッド互除法です（あとで詳述します）。

「最大公約数を求めるのなら、素因数分解をすればいいじゃないか」と思うかもしれません。

確かに、72と135のような数であれば、

というように、素因数分解をして、その素因数を比べることで、最大公約数を求めることができます。

72と135の最大公約数は9です。

しかし、素因数分解が難しい場合があります。

例えば、2627と3337の最大公約数を求めたければ、どうすればよいでしょう。

素因数分解は非常に難しいはずです。

ちなみに

ですので、2627と3337の最大公約数は71です。

ですが、37や47のような素因数を見つけるのには時間がかかり、コンピューターで計算するのでない限り、現実的ではありません。

余談ですが、素因数分解は大きな数になると、コンピューターを使っても計算量が膨大になり、「公開鍵暗号方式」など、暗号技術にも応用されています。

暗号技術は「知られたくない情報を送るための技術」ですので、簡単に解ける問題では使えません。

素因数分解をするというのは、本来それくらい計算量がいる問題なのです。

３．ユークリッド互除法の使い方を例題でマスター

ユークリッド互除法の証明をする前に、ユークリッド互除法の使い方を学んでおきましょう。

問題 288と126の最大公約数を求めよ。

回答としては以下のように書けば十分でしょう。

288＝126×2＋36
126＝36×3＋18
36＝18×2
よって、求める最大公約数は18である。

４．ユークリッド互除法の証明

なぜ、余りを考えていくことで最大公約数を求めることができるのでしょうか。
結論から言えば、以下の定理が成立するからです。

証明してみましょう。

a と b の最大公約数を
gcd⁡(a,b)
と表します。

一般に正の整数 a,b について、以下のことが成立します。

・a が b の倍数ならば、gcd⁡(a,b)＝b
・a>b のとき、gcd⁡(a,b)＝gcd⁡(a-b,b)

「 a が b の倍数ならば、gcd⁡(a,b)＝b 」が成立することは自明です。

例えば、32と8のように、32は8の倍数になっているときに、最大公約数は8ですよね。
「a>b のとき、gcd⁡(a,b)＝gcd⁡(a-b,b)」はしっかり証明しましょう。

gcd⁡(a,b)=k とすると、互いに素である正の整数 m,n (m>n) を用いて
a=km
b=kn
とおくことができます。

ここで、正の整数 m,n (m>n) が互いに素であるとき、m-n,n も互いに素であることを証明します。

(「互いに素」について詳しくはこちらの記事をご覧ください:
互いに素とは? 背理法を使った証明の例題・合同式との関係も合わせて解説)

m-n,n の最大公約数をGとすると、互いに素な正の整数 s,t を使って

m-n=sG
n=tG

とおくことができます。下の式を上の式に代入すると

m-tG=sG⇔m=G(s+t)

となります。

ここで s+t は自然数ですから、Gは m の約数です。さらに、Gは n の最大公約数ですから、n の約数でもあります。
つまり、Gは m と n の公約数になっています。

m と n は互いに素な正の整数であるなら、最大公約数 G=1 です。
Gはもともと m-n,n の最大公約数でした。
m-n と n も最大公約数が1であるような2数になるので、互いに素です。
よって「正の整数 m,n (m>n) が互いに素であるとき、m-n,n も互いに素」が証明されました。

ここで

a-b=k(m-n)
b=kn

を考えます。
m と n が互いに素なので、m-n と n も互いに素ですから、k は a-b と b の最大公約数になります。
はじめに gcd⁡(a,b)=k と置いていたので「gcd⁡(a,b)＝gcd⁡(a-b,b)」が証明されました。

a を b で割ったときの商を q、余りを r とすると、

a=bq+r 0≦r<b

です。

gcd⁡(a,b)＝gcd⁡(a-b,b)

を繰り返し用いると

gcd⁡(a,b)＝gcd⁡(bq+r,b)
=gcd⁡(bq+r-b,b)
=gcd⁡(b(q-1)+r,b)
=gcd⁡(b(q-2)+r,b)
………
＝gcd⁡(r,b)
=gcd⁡(b,r)

となります。q は正の整数ですので、b を引いてゆくことでいつか消えてしまいます。
ここから

gcd⁡(a,b)=gcd⁡(b,r)

が証明されました。
これが、この章で初めに申し上げた

2つの正の整数 a,b ( a>b) に対して、a を b で割った余りを r とするとき、a と b の最大公約数と、b と r の最大公約数は一致する。
と同義です。

つまり、次はbとrの最大公約数を調べればいいということです。さらにこれを続けていけば最終的にはaとbの最大公約数が求まるという仕組みです。

例を挙げた
288＝126×2＋36
126＝36×3＋18
36＝18×2

で言えば、288と126の最大公約数は、126と36の最大公約数に等しく、36と18の最大公約数に等しい、という意味です。
そのため、288と128の最大公約数は18になるのです。

５．ユークリッド互除法と2元1次不定方程式

「2元」とは、未知数が2つあるという意味です。
「1次」とは、最大次数が1であるという意味です。

つまり2元1次方程式とは、x,y を未知数として、

ax+by=c

です。未知数の数が2つであるのに対して、式の数が1つですので、解はただ1つに決まらず、無数にあります。
このように無数に解があるような方程式を不定方程式と言います。
ユークリッド互除法を用いて、この2元1次不定方程式の解を求めることができます。

問題 ユークリッド互除法を用いて、51x+16y=1 の解を求めよ。

６．おわりに

最後までご覧くださってありがとうございました。

この記事では、ユークリッド互除法についてまとめました。
2元1次不定方程式の特殊解が見つからないときには、ユークリッド互除法を用いて求めることができます。

慣れないとややこしいので、しっかり復習しておきましょう。

なお、これらの記事も合わせてご覧いただければ幸いです:
不定方程式とは？基礎知識と解き方を解説！
一次不定方程式の解き方! 練習問題でマスターしよう