最大公約数

最大公約数（さいだいこうやくすう、英: greatest common divisor）とは、少なくとも一つが0ではない複数の整数の公約数のうち最大の数を指す。具体的にはユークリッドの互除法により求めることができる。 しばしば「G.C.D.」や「G.C.M. (Greatest Common Measure)」、「G.C.F. (Greatest Common Factor)」、「H.C.F. (Highest Common Factor)」等の省略形で記述される。 少なくとも一つが0でない整数 a 1 , … , a n {\displaystyle a_{1},\ldots ,a_{n}} の最大公約数とは、 a 1 , … , a n {\displaystyle a_{1},\ldots ,a_{n}} の公約数のうち最大の数である。（定義から正整数となる。） つまり、 a 1 , … , a n {\displaystyle a_{1},\ldots ,a_{n}} を a j = ε j ∏ p p r i m e p e p ( j ) ( e p ( j ) ≥ 0 , ε j = ± 1 ) {\displaystyle a_{j}=\varepsilon _{j}\prod _{p\;\mathrm {prime} }p^{e_{p}(j)}\quad (e_{p}(j)\geq 0,\;\varepsilon _{j}=\pm 1)} と素因数分解したとき、 a 1 , … , a n {\displaystyle a_{1},\ldots ,a_{n}} の最大公約数は ∏ p p r i m e p min { e p ( 1 ) , … , e p ( n ) } {\displaystyle \prod _{p\;\mathrm {prime} }p^{\min\{e_{p}(1),\ldots ,e_{p}(n)\}}} で与えられる。 例えば、30 と 42 の公約数は 1, 2, 3, 6 であるから、最大公約数は 6 である。 等価であるが、整数 a 1 , … , a n {\displaystyle a_{1},\ldots ,a_{n}} の最大公約数を a 1 x 1 + ⋯ + a n x n {\displaystyle a_{1}x_{1}+\dotsb +a_{n}x_{n}} （ x 1 , … , x n {\displaystyle x_{1},\dotsc ,x_{n}} は整数） の形で表すことのできる最小の正整数と定義してもよい。（ベズーの等式参照。） 最大公約数は gcd ( a 1 , … , a n ) {\displaystyle \gcd(a_{1},\dotsc ,a_{n})} あるいは ( a 1 , … , a n ) {\displaystyle (a_{1},\dotsc ,a_{n})} などの記号で表される。 2つ以上の整数 a 1 , … , a n {\displaystyle a_{1},\ldots ,a_{n}} の最大公約数が1 であるとき、 a 1 , … , a n {\displaystyle a_{1},\ldots ,a_{n}} は互いに素であるという。 公約数は最大公約数の約数である。 証明 a , b , c , ⋯ , z {\displaystyle a,b,c,\cdots ,z} の最大公倍数を g {\displaystyle g} 、任意の公約数を d {\displaystyle d} とする． g {\displaystyle g} と d {\displaystyle d} の最小公倍数を l {\displaystyle l} とする…① このとき、 l = g {\displaystyle l=g} であることを示して証明を完了することとする． ①より l >= d {\displaystyle l>=d} 、 l >= g {\displaystyle l>=g} 。…② g , d {\displaystyle g,d} はともに a {\displaystyle a} の約数より a {\displaystyle a} は g {\displaystyle g} と d {\displaystyle d} の公倍数。 公倍数は最小公倍数の倍数であるから、 a {\displaystyle a} は l {\displaystyle l} の倍数、すなわち l {\displaystyle l} は a {\displaystyle a} の約数。 同様に g , d {\displaystyle g,d} はともに b {\displaystyle b} の約数より b {\displaystyle b} は g {\displaystyle g} と d {\displaystyle d} の公倍数。 公倍数は最小公倍数の倍数であるから、 b {\displaystyle b} は l {\displaystyle l} の倍数、すなわち l {\displaystyle l} は b {\displaystyle b} の約数。 これを c {\displaystyle c} から z {\displaystyle z} まで繰り返し、 l {\displaystyle l} は c ⋯ z {\displaystyle c\cdots z} のそれぞれに対して約数であることがわかる。 すなわち l {\displaystyle l} は a , b , c , ⋯ , z {\displaystyle a,b,c,\cdots ,z} の公約数。 公約数は最大公約数に等しいかより小さいから l <= g {\displaystyle l<=g} 。…③ ②③より l = g {\displaystyle l=g} 。これで証明を完了する。 正整数 a, b に対して、a と b の最大公約数 gcd (a, b) と最小公倍数 lcm (a, b) との間には gcd ⁡ ( a , b ) ⋅ lcm ⁡ ( a , b ) = a b {\displaystyle \operatorname {gcd} (a,b)\cdot \operatorname {lcm} (a,b)=ab} という関係がある。 しかし、この関係式は3つ以上の正整数に対しては一般には成立しない。例えば、a = 2, b = 6, c = 15 とすると、gcd (a, b, c) = 1, lcm (a, b, c) = 30 であるが、abc = 180 である。 多項式の公約数のうち、最も次数の高いものを最大公約数という。例えば、 x 3 − x {\displaystyle x^{3}-x} と x 3 + x 2 − x − 1 {\displaystyle x^{3}+x^{2}-x-1} の最大公約数は x 2 − 1 {\displaystyle x^{2}-1} である。 多項式の最大公約数は、定数倍を除いて一意に決まる。 一般にGCD整域（例えば一意分解整域）においても、最大公約数が（単元倍を除いて一意に）存在する。 ^ Hardy & Wright 2008, p. 24. ^ Hardy & Wright 2008, p. 232, Theorem 207. ^ 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.  ユークリッドの互除法 - 代表的な計算方法 公約数 公倍数 最小公倍数 多項式