メインメニューを開く
非負整数整除関係を図示した無限グラフ(ハッセ図)の一部。たとえば8と12の最大公約数は4であり、4と6の最大公約数は2である。

最大公約数(さいだいこうやくすう、: greatest common divisor)とは、少なくとも一つが0ではない複数の整数公約数のうち最大の数を指す[1]。具体的にはユークリッドの互除法により求めることができる[2]

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

定義編集

少なくとも一つが0でない整数   の最大公約数とは、  の公約数のうち最大の数である。(定義から正整数となる。)

つまり、 

 

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

 

で与えられる。

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

等価であるが、整数   の最大公約数を

   は整数)

の形で表すことのできる最小の正整数と定義してもよい。(ベズーの等式参照。)

最大公約数は   あるいは   などの記号で表される。

諸概念編集

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

公約数は最大公約数の約数である。

証明

  の最大公倍数を  、任意の公約数を   とする.   の最小公倍数を   とする…① このとき、  であることを示して証明を完了することとする. ①より   。…②   はともに   の約数より     の公倍数。 公倍数は最小公倍数の倍数であるから、   の倍数、すなわち    の約数。 同様に   はともに   の約数より     の公倍数。 公倍数は最小公倍数の倍数であるから、   の倍数、すなわち    の約数。 これを   から   まで繰り返し、   のそれぞれに対して約数であることがわかる。 すなわち    の公約数。 公約数は最大公約数に等しいかより小さいから  。…③ ②③より  。これで証明を完了する。

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

 

という関係がある[3]

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

多項式の最大公約数編集

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

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

一般の環の場合編集

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

編集

[ヘルプ]
  1. ^ Hardy & Wright 2008, p. 24.
  2. ^ Hardy & Wright 2008, p. 232, Theorem 207.
  3. ^ Hardy & Wright 2008, p. 58, Theorem 52.

参考文献編集

  • 高木貞治『初等整数論講義』共立出版、東京、1971年、第2版。
  • Hardy, G. H.; Wright, E. M. (2008) [1938]. An Introduction to the Theory of Numbers (Sixth ed.). Oxford University Press. ISBN 978-0-19-921985-8. https://books.google.com/books?id=P6uTBqOa3T4C. 

関連項目編集