最大公約数

二つの整数ａ，ｂに対して、ｂ≠０である時、

ａ＝ｑ・ｂ＋ｒ，　０≦ｒ＜｜ｂ｜

となるｑ及びｒはただ一つ定まる。このｑを商といい、ｒを余りという。ｒ＝０のとき、ａをｂの倍数といい、ｂをａの約数という。このとき記号で

ｂ｜ａ（ｂがａの約数）

と書く事がある。左側が約数で、右側が倍数である。ｃ｜ａ，ｃ｜ｂの時、ｃをａとｂの公約数という。公約数の中で最大な数を最大公約数といい、記号で（ａ，ｂ）と書く。

ユークリッドの互除法

ユークリッドの互除法とは、ｍ_１，ｎ_１の二つの自然数においてｍ_１＞ｎ_１である時

ｍ_１÷ｎ_１＝ｄ_１．．．ｅ_１

ｎ_１÷ｅ_１＝ｄ_２．．．ｅ_２

ｅ_１÷ｅ_２＝ｄ_３．．．ｅ_３

ｅ_２÷ｅ_３＝ｄ_４

と、計算して行くと、最終的に割り切れる。まずは、ｍ_１をｎ_１で割る。そして２度目からは、前の計算で割った数を、前の計算で得られた余りで割る。この作業をくり返し行なうと、最終的に割り切れる。最後に割った数がｍとｎの最大公約数となる。

では、実際に例を挙げて説明する。

例題１：１９７５と１５８の最大公約数を求める

１９７５÷１５８＝１２．．．７９

１５８÷７９＝２

ここで得られた７９が１９７５と１５８の最大公約数である。

例題２：２３０と１６３の最大公約数を求める

２３０÷１６３＝１．．．６７

１６３÷６７＝２．．．２９

６７÷２９＝２．．．９

２９÷９＝３．．．２

９÷２＝４．．．１

２÷１＝２

このことから１が２３０と１６３の最大公約数であると言え、この２数は互いに素であることが判明する。

Yahoo! Japan

Yahoo! Deutschland

This page hosted by Get your own Free Homepage