ユークリッド（Euclid)の互除法

　Fermat（フェルマー）以前に発見されていた整数論の定理で、使用頻度の高い定理ベスト2は、①ユークリッドの互除法と②中国剰余定理との2つだと思います。そのうち、今回は、ユークリッドの互除法について解説します。

　ユークリッドの互除法は、最大公約数を簡単に求める方法として紹介されることが多いです。しかし、実際にユークリッドの互除法により最大公約数を求める機会はあまりなく、むしろ、ユークリッドの互除法から導かれる最大公約数との関係式（－油分け算式－）が使用されることが圧倒的に多いです。今回は、まずは、最大公約数を求める方法としてのユークリッドの互除法をご紹介します。

1 ユークリッド互除法（最大公約数を求める方法として）

1.1 最大公約数

　まずは、最大公約数の記法につい説明します。整数\(n_{1},n_{2},\cdots,n_{k}\)の最大公約数を\((n_{1},n_{2},\cdots,n_{k})\)と書くこととします。整数の個数は複数でも単数でもよいです。また、負の数でもよいです。（負の場合は絶対値をとったうえで、最大公約数をとることとし、最大公約数は常に非負とします。）また、\(0\)と\(n\)の最大公約数は\(|n|\)とします。

（例）　\((8,12)=(-8,12)=(-8,-12)=(-8,-12)=4\)

（例）　\(n\)を整数とすると\((n)=|n|\)

（例）　\(n\)を整数とすると\((n,0)=|n|\)

（例）　\((3,6,9)=3\)

　最大公約数の定義より次の式が成り立ちます。

整数\(n,m\)に対し、

\( (n,m)=(m,n)\)

\( (n,m)=(-n,m)=(n,-m)=(-n,-m) \)

　最大公約数をこのようにカッコで記すのは一般的な記法です。ここでは、\((n,m)\)を\(n\)と\(m\)の最大公約数と定義しましたが、更に一般的には\(n\)と\(m\)から生成されるイデアル（ideal)と定義することもできます。イデアルについては別の機会に解説したいと思います。

1.2 ユークリッドの互除法

　 　最初に、最もシンプルな定式化をします。一般的には次の式を組み合わせて用いることにより最大公約数を求める方法のことをユークリッドの互除法といいます

（ユークリッドの互除法）

整数\(n,m\)に対し、 \[ (n,m)=(n-m,m)\tag{1} \]

\((n,m)=(n,-m)\)ですので、\((n,-m)\)を上の式(1)を適用することにより\((n,m)=(n+m,m)\)も成立します。また、\(n\)と\(m\)との間に大小関係を仮定する必要はありません。

1.3 式（１）の証明

　\(d=(n,m),d'=(n-m,m)\)とすると、\(d\)は\(n,m\)の公約数であるため、\(n-m,m\)の公約数である。したがって、\(d\)は\(d'\)の約数である。（公約数は最大公約数の約数であることを使っています。）

　一方、\(d'\)は\(n-m,m\)の公約数であるため\(n,m\)の公約数である。よって、\(d'\)は\(d\)の約数である。（ここでも、公約数は最大公約数の約数であることを使っています。）

　よって\(d=d'\)。

1.4 式（１）の使い方

　\((n,m)\)に、式(1)を2回繰り返すと、 \[ (n,m)=(n-2m,m)\] 3回繰り返すと \[ (n,m)=(n-3m,m)\] \(q\)回繰り返すと \[ (n,m)=(n-qm,m)\] です。 　

　必要であれば順番を入れ替え、また、負の整数は絶対値をとることにより、\(0<m<n\)とします。そのうえで、 \(n\)を\(m\)で割った商を\(q\)とし、余りを\(r\)とします。すなわち \[ n=qm+r \] とすると、 \[\begin{align} (n,m)&=(n-qm,m)\\ &=(r,m) \end{align} \]

　これがいわゆるユークリッドの互除法といわれている方法です。余りは割る数より必ず小さくできます。つまり\(n>r\)ですのでユークリッドの互除法により、必ず2つの数字のうちの1つは、元の数字より小さくできます。これを有限回繰り返すことにより、一方を0にすることができます。つまり、ユークリッドの互除法により必ず最大公約数を求めることができます。これが一般的にはユークリッドの互除法と言われているものです。

（例）\((8,12)=(12,8)=(12-8,8)=(4,8)=(8,4)=(4)=4 \)

　ユークリッドの互除法により、最大公約数を必ず求めることができるのは、「余りは割る数より必ず小さくなる」という性質を使っています。このような性質がある集合（整域）をユークリッド整域（Euclidean domain)といいます。つまり、ユークリッドの互除法により最大公約数を求めることができるのはユークリッド整域だからです。

　一方、式（１）はユークリッド整域に限らず成り立つ性質です。その意味で、より本質的なのは式（１）だと考えられます。

1.5 式（１）の応用

　ユークリッドの互除法は、最大公約数は差の最出公約数に等しいというものです。大きな数を素因数分解することは大変ですが、差をとることは簡単です。

（例）\((2015,1999)=(2015-1999,1999)=(16,1999)\) 　ここで、\(16\times125=2000\)であることから、 \((16,1999)=(1999-16\cdot125,16)=(-1,16)=1\) このように、素因数分解をすることなく1999と2015が互いに素であることが分かります。

また、\((n,n+1)=(n,1)=1\)より、連続する整数\(n,n+1\)は常に互いに素であることが一瞬で分かります。

　この性質を使って素数が無限にあることを証明したのがサイダックです。サイダックは2006年に素数が無限にあることを次のように示しました。\(n\)を2以上の自然数とするとし、\(N_{1}=n(n+1)\)とすると、\(n,n+1\)は互いに素のため\(N_{1}\)は2つ以上の異なる素数を約数としてもつ。同様に\(N_{2}=N_{1}(N_{1}+1)\)とすると、\(N_{2}\)は異なる3つ以上の素数を約数としてもつ。これを繰り返すと、任意の個数より多くの異なる素数を約数としてもつ整数を構成できる。よって、素数は無限にある。

　素数が無限にあることは、ユークリッドの時代から知られていましたが、現代においても新しい証明は発見されているようです。

　繰り返しになりますが、ユークリッドの互除法は最大公約数を効率的に求める方法です。しかし、実際には使われるのは最大公約数を求めるためよりも、最大公約数は差により保たれるという性質そのものです。その意味で重要な式（１）を再掲しておきます。

\[ (n,m)=(n-m,m)\]

　次回は、ユークリッドの互除法を用いて、最大公約数との関係式（油分け算の式）を求めてみます。