2014/04/20

ユークリッドの互除法の証明と不定方程式

分野: 整数問題  レベル: 最難関大学

ユークリッドの互除法:
自然数 $a,b \:(a\geq b)$ に対して,$a$ を $b$ で割った余りを $r$ とおくとき
gcd($a$, $b$)=gcd($b$, $r$)
が成立し,これを繰り返し用いると $a$ と $b$ の最大公約数が求まる。


「最大公約数」は画数が多くて書きたくないので,$a$ と $b$ の最大公約数のことをgcd(a,b)と表しています。難しい記号ではありません。

このページではユークリッドの互除法の証明とその応用例として1次不定方程式 $ax+by=d$ を扱います。どちらも入試では頻出のテーマです。

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

gcd($a$, $b$)=gcd($b$, $r$)であることと最終的に $a$ と $b$ の最大公約数が求まることは別々に証明する必要があります。

証明

$a$ を $b$ で割った商を $p$,余りを $r$ とおくと,
$a=bp+r$ より,
・ $a,b$ がともに $m$ の倍数→ $r=a-bp$ も $m$ の倍数。
となりgcd($a$, $b$) $\leq$ gcd($b$, $r$)
・ $b,r$ がともに $m$ の倍数→ $a=bp+r$ も $m$ の倍数。
となりgcd($a$, $b$) $\geq$ gcd($b$, $r$)
以上から,gcd($a$, $b$)=gcd($b$, $r$)

この操作を繰り返し行う。
余りの定義より $b > r$ なのでこの操作は有限回で終わり,最後は必ず余りが $0$ になって停止する。そのときの割った数がgcd($a$, $b$)になっている。

有限回で操作が終了することは例を見れば当たり前だと感じるでしょう。

$a=390,b=273$
$390=273\cdot 1+117\\
273=117\cdot 2+39\\
117=39\cdot 3+0$
よって,$390$ と $273$ の最大公約数は $39$

ユークリッドの互除法がなぜ嬉しいのか

素因数分解を利用して最大公約数を求めることもできますが,大きな数字の素因数分解よりも割り算の方が圧倒的に楽(計算量が少ない)なので応用現場ではユークリッドの互除法が用いられています。

$318691696$ と $4729749$ を素因数分解するのは相当な気合いが必要になるが割り算なら簡単にできそう。

ただし,実際の入試問題でこんなに大きな整数はほとんど登場しないので最大公約数を求めるだけだったら素因数分解を用いる方法で十分です。

ユークリッドの互除法は最大公約数を求める問題よりも,一次不定方程式 $ax+by=1$ に関する問題で活躍します。

一次不定方程式への応用

一次不定方程式 $ax+by=d$ の解を求める問題を考えます。
ただし,左辺がgcd($a$, $b$)の倍数なのでこの不定方程式が解を持つためには $d$ がgcd($a$, $b$)の倍数であることが必要です。

実はこれが十分条件にもなっています。なぜなら,

  • $d= $gcd($a$, $b$)のとき以下の例のようにユークリッドの互除法を用いて解を構成できる。
  • $d=m\cdot $gcd($a$, $b$)のときは先程の解を $m$ 倍すれば構成できる。($ax+by= $gcd($a$, $b$)→ $a(mx)+b(my)=d$)

$8x+11y=1$ の解を求める。
$11=8\cdot 1+3\\
8=3\cdot 2+2\\
3=2\cdot 1+1$
これをさかのぼっていく。(余りの部分を順々に代入していく)
$1=3-2\cdot 1\\
=3-(8-3\cdot 2)\cdot 1\\
=3\cdot 3+8\cdot(-1)\\
=(11-8\cdot 1)\cdot 3-8\\
=8\cdot (-4)+11\cdot 3$
よって,$(-4,3)$ が解の1つ。
一般解は$(-4+11n,3-8n)\:$($n$ は整数)

ポイントは,ユークリッドの互除法の式を用いて, $1$ を $2x+3y$ の形で表す→ $3x+8y$ の形で表す→ $8x+11y$ の形で表す,と変形していくことです。慣れれば機械的に計算できます。

gcdは最大(greatest) 公(common) 約数(divisor) の略

Tag: 不定方程式の解き方まとめ
Tag: 数学Aの教科書に載っている公式の解説一覧

分野: 整数問題  レベル: 最難関大学