●ユークリッドの互除法の意義
ユークリッドの互除法は、2009年に学習指導要領に導入されて以来、主として 整数2元1次不定方程式を解くためなどで、毎年出題されています。ユークリッドの互除法の本質的な意義は、計算機科学における「計算量の削減」であり、入試数学においては2元1次不定方程式を解く手法の１つであり、一方難関大で頻出の「文字式の最大公約数」などの難問を解くための強力な武器でもあります。
●ユークリッドの互除法とは、「自然数a,b (a≥b)に対して、aをbで割った余りをrとおくとき
gcd(a,b)=gcd(b,r)
が成立し，これを繰り返し用いるとaとbの最大公約数が求められる」というものです。
これの何が便利かというと、2つの数の最大公約数を求める際に、素因数分解を利用して求めることもできますが、大きな数字の場合は、素因数分解よりもユークリッドの互除法を利用した割り算の方が圧倒的に計算が容易です。またこの互除法から、2元一次不定方程式「ax+by=c」の解を求めることができます。
●ユークリッドの互除法による最大公約数の計算
[例1] a=390、b=273とすると、素因数分解ではa=390＝3・10・13、b=273=3・7・13であって、390と273の最大公約数は39です。ユークリッドの互除法では、
- 390=273・1+117
- 273=117・2+[39]
- 117=[39]・3+0
これくらいではまだ威力がわかりにくいのですが…。
[例2]a=2013、b=1159とすると、素因数分解ではa=2013＝3・11・61、b=1159=19・61となり、19も61も見つけるにはかなり大変です。しかしユークリッドの互除法では容易に61が見つかり、その後の素因数分解も容易になります。
- 2013=1159・1+854
- 1159=854・1+305
- 854=305・2+244
- 305=244・1+[61]
- 244=[61]・4
●x,yに関する二元一次不定方程式とユークリッドの互除法
ここでは補題として次の２つの定理を利用します。
【定理1】一次不定方程式が整数解を持つ必要十分条件（ベズーの定理）
a, b, c を整数とし、a と b の最大公約数を g とするとき、
「ax + by = c を満たす整数解 (x, y) が存在する」⇔ 「c は g の倍数である（c が g で割り切れる）」
【定理2】右辺が「1」の解から「c」の解への変換（解の同値変形）
a, b が互いに素な整数であるとき、任意の整数 c （≠0）について、
「ax + by = 1 の整数解を (p, q) とする」⇔「ax + by = c の特殊解の1つは (cp, cq) となる」
この【定理2】が成り立つため、「ax + by = 1」の解を求める際、 まず右辺を 1 とした「ax + by = 1」の解を求めます。必要に応じて本稿では次の英語を使います。
特殊解: special solution=ss
一般解: general solution=gs
[例題1]二元一次不定方程式（）
[例題2]
[B]既約分数の問題（2017年横浜市大／医11）
