ユークリッドの互除法のソースを表示

== 概要 ==
ユークリッドの互除法とは、大きな整数の最大公約数を早く計算する方法である。<br>
<br>
ここでは、ユークリッドの互除法とユークリッドの互除法の不定方程式への応用方法を記載する。<br>
<br><br>

== ユークリッドの互除法の性質 ==
ユークリッドの互除法では、以下の重要な性質を用いて最大公約数の計算を行う。<br>
<br>
'''重要な性質'''<br>
除算の等式 : <math>a = bq + r</math>において、"aとbの最大公約数" = "bとrの最大公約数"<br>
<br>
実際に、ユークリッドの互除法を用いて、390と273の最大公約数を計算してみる。<br>
<br>
まず、a = 390をb = 273で除算すると、q = 1、r = 117となる。<br>
<math>390 = 273 \times 1 + 117</math><br>
上記の性質より、"390と273の最大公約数" = "273と117の最大公約数"<br>
<br>
次に、a = 273をb = 117で除算する。<br>
<math>273 = 117 \times 2 + 39</math><br>
上記の性質より、"273と117の最大公約数" = "117と39の最大公約数"<br>
<br>
次に、a = 117をb = 39で除算する。<br>
<math>117 = 39 \times 3 + 0</math><br>
<br>
割り切れるということは、117と39の最大公約数は39である。<br>
<br>
以上により、390と273の最大公約数が39であることが分かる。<br>
<br>
このように、上記の性質を用いて、除算を繰り返して最大公約数を求める方法をユークリッドの互除法という。<br>
<br><br>

== ユークリッドの互除法の証明 ==
上記の重要な性質<math>gcd(a, b) = gcd(b, r)</math>を証明する。<br>
<br>
'''証明'''<br>
aをbで除算した商をq、余りをrとおくと、<math>a = bq + r</math>より、<br>
<br>
aとbがともにmの倍数ならば、<math>r = a - bq</math>もmの倍数である。<br>
よって、"aとbの公約数"は"bとrの公約数"でもある。<br>
したがって、<math>gcd(a, b) \le gcd(b, r)</math><br>
<br>
bとrがともにmの倍数ならば、<math>a = bq + r</math>もmの倍数である。<br>
よって、"bとrの公約数"は"aとbの公約数"でもある。<br>
したがって、<math>gcd(a, b) \ge gcd(b, r)</math><br>
<br>
以上、2つの不等式より、<math>gcd(a, b) = gcd(b, r)</math>となる。<br>
<br>
除算を繰り返し行うと、余りの定義より<math>b > r</math>なので、値はどんどん小さくなる。<br>
そして、最後は必ず余りが0になって終了する。<br>
その時の割った数が最大公約数になる。<br>
<br><br>

== 1次不定方程式への応用 ==
1次不定方程式<math>ax + by = 1</math>の整数解<math>(a, b)</math>を求める問題を考える。<br>
<br>
'''例'''<br>
<math>8x + 11y = 1</math>を満たす整数<math>(x, y)</math>を求める。<br>
11と8にユークリッドの互除法を適用する。<br>
<math>11 = 8 \times 1 + 3</math><br>
<math>8 = 3 \times 2 + 2</math><br>
<math>3 = 2 \times 1 + 1</math><br>
<br>
これを遡っていく。(余りの部分を順々に代入していく)<br>
<math>1 = 3 - 2 \times 1</math><br>
<math>= 3 - (8- 3 \times 2) \times 1</math><br>
<math>= 3 \times 3 + 8 \times (-1)</math><br>
<math>= (11 - 8 \times 1) \times 3 - 8</math><br>
<math>= 8 \times (-4) + 11 \times 3</math><br>
これは、<math>8x + 11y = 1</math>の形になっている。<br>
つまり、<math>(-4, 3)</math>が解の1つとなる。<br>
<br>
したがって、1次不定方程式<math>ax + by = 1</math>の整数解にあるように、<br>
解が1つ見つかれば一般解が構成できる。<br>
一般解は、<math>(-4 + 11n, 3 - 8n)  \mbox{( n  は  整  数  )}</math><br>
<br>
ポイントは、ユークリッドの互除法の式を用いて、<br>
1を<math>2x + 3y</math>の形で表す。→<math>3x + 8y</math>の形で表す。→<math>8x + 11y</math>の形で表す。<br>
と変形していくことである。<br>
<br><br>

__FORCETOC__
[[カテゴリ:暗号理論]]