ユークリッドの互除法の簡易解法 - 小西研究室@電脳工房ＭＳＣ

ユークリッドの互除法

０でない2つの整数 $a,b$ に対して、商を $q$ 、余りを $r_1$ とするとき、
　　 $a\div b=q\dots r_1$ 　⇔　 $a=bq+r_1$
となる。このとき、 $a,b$ の最大公約数 $(a,b)$ に対して、 $(a,b)=(b,r_1)$ が成り立つ。
この性質を利用して、商と余りを求める操作を繰り返すと、最終的に $(d,0)=d$ となる。

定理

０でない2つの整数 $a,b$ の最大公約数を $d$ とするとき、
　　　 $d=ka+lb$
となる整数 $k,l$ が存在する。

「ユークリッドの互除法の簡易解法」をウィキ内検索

最終更新：2011年12月12日 18:51