수론에서, 정수들의 공약수(公約數, 영어: common factor)는 동시에 그들 모두의 약수인 정수다. 적어도 하나가 0이 아닌 정수들의 최대공약수(最大公約數, 문화어: 련속나눔셈; 영어: greatest common factor, 약자 GCF)는 공약수 가운데 가장 큰 하나다. 다항식이나 환의 원소에 대해서도 정의할 수 있다.
최대공약수는 각 정수의 약수를 구하고, 공통되는 약수를 구하고, 가장 큰 하나를 구하면 얻을 수 있다. 예를 들어 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)다. 또한 유일 인수분해정역에서는 영이 아닌 두 원소의 경우 항상 최대공약수가 존재한다.
서보억 (2011년 10월 10일). “최대공약수”. 《네이버캐스트》. 2013년 8월 27일에 원본 문서에서 보존된 문서. 2018년 5월 10일에 확인함.
This article uses material from the Wikipedia 한국어 article 최대공약수, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). 별도로 명시하지 않은 경우, 내용은 CC BY-SA 4.0에 따라 사용할 수 있습니다. Images, videos and audio are available under their respective licenses. ®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki 한국어 (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.