ユークリッドの互除法

概要

ユークリッドの互除法とは、大きな整数の最大公約数を早く計算する方法である。

ここでは、ユークリッドの互除法とユークリッドの互除法の不定方程式への応用方法を記載する。

ユークリッドの互除法の性質

ユークリッドの互除法では、以下の重要な性質を用いて最大公約数の計算を行う。

重要な性質
除算の等式 : $a=bq+r$において、"aとbの最大公約数" = "bとrの最大公約数"

実際に、ユークリッドの互除法を用いて、390と273の最大公約数を計算してみる。

まず、a = 390をb = 273で除算すると、q = 1、r = 117となる。
$390=273\times 1+117$
上記の性質より、"390と273の最大公約数" = "273と117の最大公約数"

次に、a = 273をb = 117で除算する。
$273=117\times 2+39$
上記の性質より、"273と117の最大公約数" = "117と39の最大公約数"

次に、a = 117をb = 39で除算する。
$117=39\times 3+0$

割り切れるということは、117と39の最大公約数は39である。

以上により、390と273の最大公約数が39であることが分かる。

このように、上記の性質を用いて、除算を繰り返して最大公約数を求める方法をユークリッドの互除法という。

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

上記の重要な性質$gcd(a,b)=gcd(b,r)$を証明する。

証明
aをbで除算した商をq、余りをrとおくと、$a=bq+r$より、

aとbがともにmの倍数ならば、$r=a-bq$もmの倍数である。
よって、"aとbの公約数"は"bとrの公約数"でもある。
したがって、$gcd(a,b)\le gcd(b,r)$

bとrがともにmの倍数ならば、$a=bq+r$もmの倍数である。
よって、"bとrの公約数"は"aとbの公約数"でもある。
したがって、$gcd(a,b)\ge gcd(b,r)$

以上、2つの不等式より、$gcd(a,b)=gcd(b,r)$となる。

除算を繰り返し行うと、余りの定義より$b>r$なので、値はどんどん小さくなる。
そして、最後は必ず余りが0になって終了する。
その時の割った数が最大公約数になる。

1次不定方程式への応用

1次不定方程式$ax+by=1$の整数解$(a,b)$を求める問題を考える。

例
$8x+11y=1$を満たす整数$(x,y)$を求める。
11と8にユークリッドの互除法を適用する。
$11=8\times 1+3$
$8=3\times 2+2$
$3=2\times 1+1$

これを遡っていく。(余りの部分を順々に代入していく)
$1=3-2\times 1$
$=3-(8-3\times 2)\times 1$
$=3\times 3+8\times (-1)$
$=(11-8\times 1)\times 3-8$
$=8\times (-4)+11\times 3$
これは、$8x+11y=1$の形になっている。
つまり、$(-4,3)$が解の1つとなる。

したがって、1次不定方程式$ax+by=1$の整数解にあるように、
解が1つ見つかれば一般解が構成できる。
一般解は、$(-4+11n,3-8n)\text{( n は 整 数 )}$

ポイントは、ユークリッドの互除法の式を用いて、
1を$2x+3y$の形で表す。→$3x+8y$の形で表す。→$8x+11y$の形で表す。
と変形していくことである。