最終更新:2019/05/01

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

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

ユークリッドの互除法(ごじょほう)とは,大きな数字たちの最大公約数を素早く計算する方法です。

この記事では,ユークリッドの互除法のやり方ユークリッドの互除法の不定方程式への応用方法などを解説します。

ユークリッドの互除法の例

ユークリッドの互除法では,以下の重要な性質を使って最大公約数の計算を行います。

重要な性質:
割り算の等式:$a=bq+r$ において,
「$a$ と $b$ の最大公約数」
=「$b$ と $r$ の最大公約数」

例えば,ユークリッドの互除法を使って $390$ と $273$ の最大公約数を計算してみましょう。

まず,$390$ を $273$ で割ると,商が $1$ で余りが $117$ です:
$390=273\cdot 1+117$

よって,重要な性質より
「$390$ と $273$ の最大公約数」
=「$273$ と $117$ の最大公約数」

次に,$273$ を $117$ で割ります:
$273=117\cdot 2+39$

よって,重要な性質より
「$273$ と $117$ の最大公約数」
=「$117$ と $39$ の最大公約数」

次に,$117$ を $39$ で割ります:
$117=39\cdot 3+0$

割り切れました! つまり「$117$ と $39$ の最大公約数」は $39$ です。以上により「$390$ と $273$ の最大公約数」が $39$ であることが分かりました。

このように,重要な性質を使って,繰り返し(割り切れるまで)割り算をしていき最大公約数を求める方法をユークリッドの互除法と言います。

最大公約数の記号

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

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

ユークリッドの互除法で用いた,

重要な性質:
$\mathrm{gcd}(a, b)=\mathrm{gcd}(b,r)$

を証明します。

証明

$a$ を $b$ で割った商を $q$,余りを $r$ とおくと,
$a=bq+r$ より,

・ $a,b$ がともに $m$ の倍数→ $r=a-bq$ も $m$ の倍数。
よって「$a$ と $b$ の公約数」は「$b$ と $r$ の公約数」でもある。したがって,
$\mathrm{gcd}(a, b)\leq\mathrm{gcd}(b,r)$

・ $b,r$ がともに $m$ の倍数→ $a=bq+r$ も $m$ の倍数。
よって「$b$ と $r$ の公約数」は「$a$ と $b$ の公約数」でもある。したがって,
$\mathrm{gcd}(a, b)\geq\mathrm{gcd}(b,r)$

以上2つの不等式より,$\mathrm{gcd}(a, b)=\mathrm{gcd}(b,r)$

割り算を繰り返し行うと,余りの定義より $b > r$ なので数字はどんどん小さくなっていきます。そして,最後は必ず余りが $0$ になって停止します。そのときの割った数が,求めたい最大公約数になっています。

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

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

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

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

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

一次不定方程式への応用

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

$8x+11y=1$ を満たす整数 $(x,y)$ を求める。

$11$ と $8$ にユークリッドの互除法を適用してみる。
$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$

これは $8x+11y=1$ の形になっている
つまり,$(-4,3)$ が解の1つ。

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

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

まとめ

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

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

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