2.1.2 ユークリッドの互除法

この項では、ユークリッドの互除法により必ず最大公約数を求めることができることをしめします。

次の補題はユークリッドの互除法を使ううえで基本となるものです。

補題 2.1.10 (除法の原理（商と余りの関係）)

を整数とするとき、整数

をうまくとることにより

$\displaystyle m=qn+r, \hspace{1.5cm} \vert r\vert<\vert n\vert$

とすることができる。

証明

が正のときは、

を

で割った商を

、余りを

とすればよい。

のいづれか又は両方が負の数であるときは各自確かめてください。。

例 2.1.11
16を3で割った商は5で、余りは1です。これを式で書けば、 $16=5\times 3+1$ です。

補題 2.1.10は、(少なくとも

と

が正の整数の場合は）当然に成り立つ式です。ここで、わざわざこの当然の式を補題としたのは、この補題が素因数分解の一意性に重要な役割を果たすからです。今後、整数の世界を拡張しますが、この式がなりたつような体系は、素因数分解の一意性が成立することが分かります。

Remark 2.1.12
詳細は後に見ますが補題 2.1.10が成り立つ体系を「ユークリッド整域」といい、ユークリッド整域は素因数の一意性が成立することが示せます。ガウス整数 $\{n+mi \vert n,mは整数\}$ やアイゼンシュタインの整数 $\{n+m\omega\vert n,mは整数, \omega:\omega^2+\omega+1=0\}$ は、補題 2.1.10が成立しているため、ユークリッド整域になります。したがって、素因数分解の一意性も成り立っています。
これに対し、 $\{n+m\sqrt{-5}\hspace{0.3cm}\vert n,m:$ 整数 $\}$ では補題 2.1.10は成立せず素因数分解の一意性も成り立ちません。

定義 2.1.13

を整数とする。

に対し次の操作を有限回繰り返すことにより最大公約数を求める方法をユークリッドの互除法（Euclidean algorithm）という。（1）から（4）の式は、命題 2.1.6により成り立つことが分かります。
（1）

（2）

（3）

（4）

整数

の最大公約数は、ユークリッドの互除法により求められることを確かめましょう。

操作（2）により、

は正と仮定しても一般性を失いませんし、操作（1）より

としても一般性を失いません。補題 2.1.10より $\vert r\vert<\vert n\vert$ となる

をうまくとることにより

とすると、操作（3）より

とできます。このように $(n,m)\rightarrow(n,r)$ と変形することができました。

ですのでより小さな数の最大公約数に帰着することができます。

に対し、操作（1）、（3）を繰り返すことにより、より小さい数の最大公約数に帰着できますので、いつか一方が0になります。すると操作（4）より、0でない数が最大公約数と分かります。

定理 2.1.14

を整数とすると、ユークリッドの互除法により最大公約数

を必ず求めることができる。　

3つ以上の整数の最大公約数も同様の方法で必ず求めることができます。

例 2.1.15
123と35の最大公約数を求めてみましょう。123を35で割ると、 $123=3\times35+18$ ですね。これを使うと、 $(35,123)=(35,123-3\times35)=(35,18)$ です。次に、35を18でわると、 $35=1\times18+17$ ですね。すると

です。したがって、

であり、123と35は互いに素であることが分かります。
これは、素因数分解 $35=5\cdot 7, 123=3\cdot 41$ からも分かります。

例 2.1.16

$\displaystyle (356,254)$	$\displaystyle =$	$\displaystyle (356-254,254)=(254,102)=(254-2\times 102,102)$
	$\displaystyle =$	$\displaystyle (102,50)=(102-2\times 50,50)=(50,2)=2$

このように、ユークリッドの互除法は大きな数の最大公約数を求めることができる点で実用的です。しかも、ユークリッドの互除法が重要なのはそれだけではありません。次講では理論的な観点からも重要であることが分かります。