最大公約数

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索
40と15に関する次の要素が埋め込まれた図: 積(600)、 商と剰余(40÷15=2余り10)、 最小公倍数(120)、 最大公約数(5)、 (8:3)
幾何学的に2つの整数(WとH)及びその最大公約数並びに最小公倍数を長さとして表せる。この図では、WとHを長方形の幅と高さに割り当て、最大公約数をユークリッドの互除法に基づく方法で長さとして求めだし、長方形の面積(WとHの積)を最大公約数で割った結果として最小公倍数も長さとして求めだしている。

最大公約数(さいだいこうやくすう、: greatest common divisor)とは、少なくとも1個が0ではない複数の整数公約数のうち最大のものを指す。

しばしば「G.C.D.」や「G.C.M. (Greatest Common Measure)」、「G.C.F. (Greatest Common Factor)」、「H.C.F. (Highest Common Factor)」等の省略形で記述される。

定義[ソースを編集]

2つ以上の整数 の最大公約数とは、 の公約数のうち最大の正整数である。

つまり、

素因数分解したとき、 の最大公約数は

で与えられる。

例えば、30 と 42 の公約数は 1, 2, 3, 6 であるから、最大公約数は 6 である。

諸概念[ソースを編集]

2つ以上の整数 の最大公約数が1 であるとき、互いに素であるという。

正整数 a, b に対して、ab の最大公約数 gcd (a, b)最小公倍数 lcm (a, b) との間には

という関係がある。

しかし、この関係式は3つ以上の正整数に対しては一般には成立しない。例えば、a = 2, b = 6, c = 15 とすると、gcd (a, b, c) = 1, lcm (a, b, c) = 30 であるが、abc = 180 である。

多項式の最大公約数[ソースを編集]

多項式の公約数のうち、最も次数の高いものを最大公約数という。例えば、 の最大公約数は である。

多項式の最大公約数は、定数倍を除いて一意に決まる。

一般の環の場合[ソースを編集]

一般にGCD整域(例えば一意分解整域)においても、最大公約数が(単元倍を除いて一意に)存在する。

参考文献[ソースを編集]

  • 高木貞治 『初等整数論講義第2版』 共立出版、東京、1971年

関連項目[ソースを編集]