[2] ユークリッドの互除法

 この主題は、新学習指導要領において、整数問題が数Aに登場した際に、同時に登場しました。ユークリッドの互除法とは、
「自然数a,b (a≥b)に対して、aをbで割った余りをrとおくとき　
　　　　　　　　　　gcd(a,b)=gcd(b,r)
が成立し，これを繰り返し用いるとaとbの最大公約数が求められる」というものです。
 これの何が便利かというと、2つの数の最大公約数を求める際に、素因数分解を利用して求めることもできますが、大きな数字の場合は、素因数分解よりもユークリッドの互除法を利用した割り算の方が圧倒的に計算量が容易です。またこの互除法から、一次不定方程式ax+by=dの解を求めることができます。
ユークリッドの互除法の証明
■［x,yに関する二元一次不定方程式］
これにも２つの定理があります。
ax+by=1が整数解を持つ⇔aとbは互いに素
ax+by=cが整数解を持つ⇔cはgcd(a,b)の倍数（ベズーの等式）
1次不定方程式の諸定理の証明  

●ユークリッドの互除法による最大公約数の計算
[例1] 
a=390
b=273
とすると、素因数分解ではa=390＝3・10・13、b=273=3・7・13ですが、ユークリッドの互除法では、 

• 390=273・1+117
• 273=117・2+[39]
• 117=[39]・3+0

したがって、390と273の最大公約数は39です。これくらいではまだ威力がわかりにくいのですが…。
[例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

［例題］

[B]既約分数の問題（2017年横浜市大／医） 
 

［入試問題］
[B]ユークリッドの互除法の問題（2016年慶応大／医12）

[D]複素数とユークリッド互除法の問題（2016年慶応大／理工4）


●ユークリッドの互除法による不定方程式の解法
[B]不定方程式の例題（新作問題）
 
[B]不定方程式の問題（2017年慶応大／医12）