2020年3月21日数学最大公約数,ユークリッドの互除法,拡張ユークリッドの互除法,1次方程式

最大公約数を求める高速なアルゴリズムとしてユークリッドの互除法が知られています。このユークリッドの互除法を拡張することにより、

$$ ax+by=gcd(a,b)$$

の形をした、2変数の一次方程式の整数解を求 ...