수론에서, 정수들의 최대 공약수(最大公約數, 문화어: 련속나눔셈; 영어: greatest common divisor/factor, 약자 GCD/GCF)는 모든 정수들의 약수가 되는 양의 정수 가운데 가장 큰 하나다. (가장 큰 하나가 없는 경우는 모든 정수가 0인 경우뿐이며, 이 경우 최대 공약수를 0으로 정의한다.) 정수 집합의 약수 관계에 대한 (완비) 원격자에서의 상한이다. 기호는 또는 .
최대 공약수는 임의의 정수에 대하여 정의된다.[1]:14, Theorem 1.2 일부 문헌에서는 0이 아닌 정수를 하나 이상 포함하는 경우에만 최대 공약수를 정의한다. (이는 최대 공약수가 문자 그대로 가장 큰 공통의 약수가 되는 경우이다.) 일부 문헌에서는 0이 아닌 정수를 요구하며, 다른 일부 문헌에서는 양의 정수를 요구하기도 한다.
다항식이나 가환환의 원소에 대해서도 정의할 수 있다. 정수의 최대 공약수를 음이 아닌 정수로 정하는 것처럼, 다항식의 최대 공약수는 (0 또는) 일계수 다항식으로 정한다. 가환환의 원소의 경우, 추가적인 데이터가 없는 한 최대 공약수를 표준적으로 고르는 방법은 정해져 있지 않다.
정수들의 공약수(公約數, 영어: common divisor/factor)는 동시에 그들 모두의 약수인 정수다. 두 정수의 공약수는 의 약수이자 의 약수인 정수이다. 두 정수 의 최대 공약수는 다음과 같은 여러 정의가 있으며, 이들은 서로 동치이다.[1]:14, Theorem 1.2
이거나 인 경우, , 의 가장 큰 공약수. 인 경우, 0.
1은 공약수이므로 공약수 집합은 공집합이 아니다. 0이 아닌 정수의 약수 집합은 유한 집합이므로, 0이 아닌 정수를 하나 이상 포함하는 두 정수의 공약수 집합도 유한 집합이다. 따라서, 최대 원소가 존재한다. 두 정수 모두 0인 경우, 공약수 집합은 모든 정수의 집합이므로 최대 원소가 존재하지 않으며, 따라서 별도로 정의한다.
, 의 공약수이며, , 의 모든 공약수의 배수인 정수는 항상 의 꼴로 나타난다. 따라서, 이 가운데 음이 아닌 정수는 유일하다. 이 정의는 임의의 두 정수에 대하여 유효하므로, 경우를 나눌 필요가 없다.
, 의 공약수이며, , 의 정수 계수 선형 결합으로 나타낼 수 있는 유일한 음이 아닌 정수
마찬가지로, , 의 공약수이며, , 의 정수 계수 선형 결합으로 나타낼 수 있는 정수는 의 꼴로 나타나며, 이 가운데 음이 아닌 하나를 고른다. 이 정의는 유클리드 호제법에 의한다. 이 정의는 임의의 두 정수에 대하여 유효하므로, 경우를 나눌 필요가 없다.
이거나 인 경우, , 의 정수 계수 선형 결합인 최소 양의 정수. 인 경우, 0.
이는 베주 항등식을 통한 정의이다. 두 정수 모두 0인 경우, , 의 정수 계수 선형 결합은 0뿐이므로, 별도로 정의한다.
보다 일반적으로, 유한 개의 정수 의 공약수는 모든 의 배수인 정수이다. 유한 개의 정수 의 최대 공약수는 다음과 같은 서로 동치인 정의가 있다. 이는 항상 유일하게 존재한다.
가장 큰 공약수. (단, 인 경우 .)
공약수이며, 모든 공약수의 배수인 유일한 음이 아닌 정수
공약수이며, 정수 계수 선형 결합인 유일한 음이 아닌 정수
0이 아닌 정수를 포함하는 경우, 정수 계수 선형 결합인 최소 양의 정수. (단, 인 경우 .)
이 정의는 재귀적이며, 두 정수의 최대 공약수의 정의에 의존한다.
보다 일반적으로, (무한 집합일 수 있는) 임의의 정수 집합 의 최대 공약수를 정의할 수 있다. 유한 개의 정수에 대한 정의들은 재귀적 정의를 제외하면 무한 개의 정수에 대해서도 (적절한 수정을 거치면) 유효하다. 이 경우, 모든 정수가 0인 경우는 이거나 인 경우에 해당한다.
일부 문헌에서는 최대 공약수의 정의를 적어도 하나 이상의 정수가 0이 아닌 경우로 제한한다. 일부 문헌은 0이 아닌 정수의 경우로 제한한다. 일부 문헌은 양의 정수로 제한한다.
최대 공약수는 각 정수의 약수를 구하고, 공통되는 약수를 구하고, 가장 큰 하나를 구하면 얻을 수 있다. 예를 들어 12와 18의 경우, 12의 모든 약수는 (±) 1, 2, 3, 4, 6, 12이며, 18의 모든 약수는 (±) 1, 2, 3, 6, 9, 18이므로, 공약수는 (±) 1, 2, 3, 6이다. 가장 큰 6이 바로 최대 공약수이다. 최대 공약수를 구하는 방법은 그 밖에 소인수분해를 통한 방법과 유클리드 호제법을 통한 방법이 있다.
임의의 환 위에서 최대 공약수를 정의할 수 있다. 가환 환에서 두 원소 와 에 대하여 가 최대 공약수라 함은 가 두 원소의 약수이며 동시에 임의의 공약수는 의 약수가 됨을 말한다. 그러나 이렇게 정의할 경우 최대 공약수는 유일하지 않을 수도 있고 두 원소가 영이아니라 하더라도 존재하지 않을 수도 있다. 정역에서는 일단 존재한다면 최대 공약수들은 서로 동반된(associated)다. 또한 유일 인수분해정역에서는 영이 아닌 두 원소의 경우 항상 최대 공약수가 존재한다.