최대공약수

수론에서, 정수들의 공약수(公約數, )는 동시에 그들 모두의 약수인 정수다. 적어도 하나가 0이 아닌 정수들의 최대공약수(最大公約數, ; , 약자 GCF)는 공약수 가운데 가장 큰 하나다. 다항식이나 환의 원소에 대해서도 정의할 수 있다.

정의 
두 정수 의 공약수는 의 약수이자 의 약수인 정수이다. 모두 0이 아닌 두 정수 의 최대공약수는 다음과 같은 여러 정의가 있으며, 이들은 서로 동치이다.
 , 의 가장 큰 공약수
 , 의 공약수이자, , 의 모든 공약수의 배수인 양의 정수
 , 의 정수 계수 선형 결합인 최소 양의 정수
모두 0이지는 않은 두 정수의 최대공약수는 항상 존재하며, 항상 유일하다. 기호는  또는 .

비슷하게, 여러 정수 의 공약수는 공통 약수이며, 모두 0이지는 않은 여러 정수 의 최대공약수 는 다음과 같은 서로 동치인 정의가 있다. 이는 항상 유일하게 존재한다.
 가장 큰 공약수
 공약수이자, 모든 공약수의 배수인 양의 정수
 정수 계수 선형 결합인 최소 양의 정수
 (재귀적 정의) 

최대공약수가 1인 정수들을 서로소라고 한다.

성질 
최대공약수는 다음과 같은 성질들을 가진다. (여기서 최대공약수를 취하는 정수들은 적어도 하나가 0이 아니라고 가정한다.)

약수 관계는 최대공약수를 통해 다음과 같이 나타낼 수 있다.

공약수는 최대공약수의 약수와 동치이다.

최대공약수는 정수 계수 선형 결합으로 나타낼 수 있는 최소 양의 정수이다.

최대공약수는 음이 아닌 정수 에 대하여 다음과 같다.

특히, 정수들을 최대공약수로 나눈 몫들은 서로소다.

정수들 가운데 하나에서 다른 하나와 서로소인 약수를 지워도 최대공약수가 변하지 않는다.

소인수분해가 주어진 정수들의 최대공약수는 공통된 소인수의 최소 지수 거듭제곱의 곱이다. 두 정수의 경우 소인수분해가 다음과 같다고 하자.

그렇다면, 최대공약수는 다음과 같다.

두 정수의 최대공약수와 최소공배수의 관계는 다음과 같다.

계산 
최대공약수는 각 정수의 약수를 구하고, 공통되는 약수를 구하고, 가장 큰 하나를 구하면 얻을 수 있다. 예를 들어 12와 18의 경우, 12의 모든 약수는 (±) 1, 2, 3, 4, 6, 12이며, 18의 모든 약수는 (±) 1, 2, 3, 6, 9, 18이므로, 공약수는 (±) 1, 2, 3, 6이다. 가장 큰 6이 바로 최대공약수이다. 최대공약수를 구하는 방법은 그 밖에 소인수분해를 통한 방법과 유클리드 호제법을 통한 방법이 있다.

소인수분해 

두 수 192와 72의 최대공약수를 소인수 분해를 이용하여 구하여 보자. 일단 두 수를 소인수 분해한다.

구하고 나면, 두 소인수 분해 결과의 중복되는 부분을 찾아 서로 곱한다. 두 결과에서 2가 세 번 중복되어 나오고 3이 한번 중복되어 나왔다. 즉  최대공약수가 24라는 결론이 나온다.

그러나 일반적으로 소인수 분해를 효율적으로 빠른 시간 내에 하는 방법은 알려져 있지 않다. 더 빠른 시간 안에 구하는 방법에는 호제법이 있다.

유클리드 호제법 

똑같이 두 수 192와 72의 최대공약수를 이번에는 호제법으로 구하여 보자. 일단 192을 72로 나누어 나머지를 구한다.

이는 192을 72로 나누어 나온 나머지가 48라는 것을 의미한다. 이번에는 72을 나머지인 48로 나눈다.

이와 같은 연산을 나머지가 0이 될 때까지 반복한다.

나머지가 0이 되었으므로 연산을 중지한다. 이때, 나머지가 0이 되기 바로 직전의 연산에서의 나머지가 원래 두 수의 최대공약수가 된다.

이를 수식화 한 것은 호제법 문서를 참조하라.

관련 개념 
임의의 환 위에서 최대공약수를 정의할 수 있다. 가환 환에서 두 원소 와 에 대하여 가 최대공약수라 함은 가 두 원소의 약수이며 동시에 임의의 공약수는 의 약수가 됨을 말한다. 그러나 이렇게 정의할 경우 최대공약수는 유일하지 않을 수도 있고 두 원소가 영이아니라 하더라도 존재하지 않을 수도 있다. 정역에서는 일단 존재한다면 최대공약수들은 서로 동반된(associated)다. 또한 유일 인수분해정역에서는 영이 아닌 두 원소의 경우 항상 최대공약수가 존재한다.

같이 보기 
 최소공배수

외부 링크 
 

곱셈적 함수