2015/01/10高校1・2年生に向けた大学受験対策～数学編（ユークリッドの互除法）～

高校生の数学を教えていて、「ユークリッドの互除法がよくわからない」という声をよく耳にします。
方法をなんとなく覚えていて、類題を解くことはできても形式が変わってしまうと手が止まってしまう生徒が多くいます。
今回はそんなユークリッドの互除法の基本とそれを応用した1次不定方程式の解き方を述べたいと思います。

 

1．ユークリッドの互除法とは

ユークリッドの互除法は「2つの自然数の最大公約数を求める方法の1つ」です。
最大公約数を求めるとき、小さい数は簡単ですが、大きな数同士となると約数を求めるだけでも苦労してしまいます。そんなときに役立つ方法としてこの手法が採用されます。

 

題　自然数 a, bの最大公約数をユークリッドの互除法を用いて求める

基本原理

(1) aを bで表す。（aを bで割ると a = bq + r）
このとき、＜aと bの最大公約数＞ = ＜bと rの最大公約数＞

(2) bを rで表す。 (bを rで割ると b = rp + s)
このとき、＜aと bの最大公約数＞ = ＜bと rの最大公約数＞ = ＜rと sの最大公約数＞

この調子で最大公約数を簡単に求められる数まで、ペアの数を小さくしていきます。
これがユークリッドの互除法です。

例題　421と322の最大公約数をユークリッドの互除法を用いて求めよ。

解答

421 = 322× 1 + 99 　　　＜422と 322の最大公約数＞ = ＜322と 99の最大公約数＞ 　
322 = 99× 3 + 25 　　　＜322と 99の最大公約数＞ = ＜99と 25の最大公約数＞
99 = 25× 3 + 24 　　　＜99と 25の最大公約数＞ = ＜25と 24の最大公約数＞
25 = 24× 1 + 1 　　　＜25と 24の最大公約数＞ = ＜24と 1の最大公約数＞ = 1

答え. 1

2. 1次不定方程式とユークリッドの互除法

1.でユークリッドの互除法の手法について解説しました。
2つの自然数の最大公約数を求める手法であるユークリッドの互除法ですが、これを応用することで1次不定方程式の解の1つを求めることができます。

題　ax + by = 1 (a, bは互いに素)を満たす整数の組 (x, y)の組をユークリッドの互除法を用いて求める

基本原理

(1) aを bを用いて表す。
a = bq + r

(2) aと bが互いに素なので、２回の操作で終了する。

b = rp + 1

(3)(1), (2)の式を変形する。
r = a - bq
-rp + b = 1

(4) 上式を下式に代入し、rを消去する。
- (a - bq) p + b = 1
a (- p) + b (pq + 1) = 1

解の 1つ (x, y) = (-p, pq + 1)

このようにユークリッドの互除法を2回行い、式変形することで1次不定方程式の解を求めることができます。

例題　5x + 3y = 1 を満たす整数の組 (x, y)の組をユークリッドの互除法を用いて求めよ。

解答

5=3×1+2 (*)　 　＜5と3の最大公約数＞ = ＜3と2の最大公約数＞

3=2×1+1 (**)　　＜3と2の最大公約数＞ = ＜2と1の最大公約数＞=1

(*)を変形して
2=5-3× 1 (***)

(**)を変形して
(- 1)×2+3=1 (****)

(***)を (****) へ代入　＜2を消去する＞
5×(- 1)+3×2= 1

答え. 解の 1つ (x, y) = (-1, 2)

一見難しそうなユークリッドの互除法ですが、手法の手順は一つです。
「覚える量は最小に、応用範囲は最大に」を意識して問題に取り組んでいきましょう。