ユークリッドの互除法
要点
割り算と最大公約数
自然数a, bについて, aをbで割ったときの商をq, 余りをrとすると
aとbの最大公約数は, bとrの最大公約数に等しい。
ユークリッドの互除法
上記の定理を繰り返し用いると, 2つの整数の最大公約数を求めることができる。
[1] aをbで割った余りをrとする。
[2] r=0なら bがaとbの最大公約数である。
r≠0なら rをbに, bをaに置き換えて[1]に戻る。
これを繰り返して余りが0になったときの割る数が最大公約数となる。
このようにして最大公約数を求める方法をユークリッドの互除法または単に互除法という。
互いに素である整数の性質
互除法の計算を利用すると, 互いに素である2つの整数について
ax+by=1 を満たす整数x, yが必ず存在する。
したがって,任意の整数cについて
ax+by=cを満たす整数x,yも存在する。