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

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

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

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

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

重要な性質

割り算の等式:a=bq+ra=bq+r において,「aabb の最大公約数」=「bbrr の最大公約数」

ユークリッドの互除法を使って 390390273273 の最大公約数を計算してみましょう。

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

  1. まず,390390273273 で割ると,商が 11 で余りが 117117 です。 390=273×1+117 390 = 273\times 1+117 よって,重要な性質 より
    390390273273 の最大公約数」 =「273273117117 の最大公約数」

  2. 次に,273273117117 で割ります。 273=117×2+39 273=117\times 2+39 よって,重要な性質 より
    273273117117 の最大公約数」 =「1171173939 の最大公約数」

  3. 次に,1171173939 で割ります。 117=39×3+0 117=39\times 3+0 割り切れました! つまり「1171173939 の最大公約数」は 3939 です。

以上により「390390273273 の最大公約数」が 3939 であることが分かりました。

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

最大公約数の記号

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

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

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

重要な性質:

gcd(a,b)=gcd(b,r) \mathrm{gcd} (a, b)=\mathrm{gcd} (b,r)

を証明します。

証明

aabb で割った商を qq,余りを rr とおくと,a=bq+r a = bq + r となる。

gcd(b,r)gcd(a,b)\mathrm{gcd}(b,r) \geq \mathrm{gcd}(a,b)

gcd(a,b)gcd(b,r)\mathrm{gcd}(a,b) \geq \mathrm{gcd}(b,r)

が似たような方法で証明できる (*) ので,

gcd(a,b)=gcd(b,r)\mathrm{gcd}(a,b) = \mathrm{gcd}(b,r)

がわかる。

(* 上側の不等式の証明)

aabbgcd(a,b)\mathrm{gcd}(a,b) の倍数なので,r=abqr = a-bqgcd(a,b)\mathrm{gcd}(a,b) の倍数になる。よって,gcd(a,b)\mathrm{gcd}(a,b)bbrr の公約数。最大公約数は公約数の中で最大のものなので,

gcd(b,r)gcd(a,b)\mathrm{gcd}(b,r) \geq \mathrm{gcd}(a,b)

(* 下側の不等式の証明)

bbrrgcd(b,r)\mathrm{gcd}(b,r) の倍数なので,a=bq+ra = bq + rgcd(b,r)\mathrm{gcd}(b,r) の倍数になる。よって,gcd(b,r)\mathrm{gcd}(b,r)aabb の公約数。最大公約数は公約数の中で最大のものなので,

gcd(a,b)gcd(b,r)\mathrm{gcd}(a,b) \geq \mathrm{gcd}(b,r)

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

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

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

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

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

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

一次不定方程式への応用

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

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

111188 にユークリッドの互除法を適用してみる。

11=81+38=32+23=21+1\begin{aligned} 11&=8\cdot 1+3\\ 8&=3\cdot 2+2\\ 3&=2\cdot 1+1 \end{aligned}

これをさかのぼっていく(余りの部分を順々に代入していく)。

1=321=3(832)1=33+8(1)=(1181)38=8(4)+113\begin{aligned} 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 \end{aligned}

これは 8x+11y=18x+11y=1 の形になっている

つまり,(4,3)(-4,3) が解の1つ。

よって,一次不定方程式ax+by=cの整数解にあるように, 解が1つ見つかれば一般解が構成できる:

一般解は (4+11n,38n)(-4+11n,3-8n)\: (nn は整数)

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

まとめ

ユークリッドの互除法

自然数 a,b(ab)a,b \:(a\geq b) に対して,aabb で割った余りを rr とおくとき gcd(a,b)=gcd(b,r)\mathrm{gcd}(a, b)=\mathrm{gcd}(b,r) が成立し,これを繰り返し用いると aabb の最大公約数が求まる。

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

Tag:不定方程式の解き方まとめ

Tag:数学Aの教科書に載っている公式の解説一覧