최대공약수

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

최대공약수(最大公約數)란, 0이 아닌 두 정수다항식의 공통되는 약수 중에서 가장 큰 수를 말한다. 두 정수 ab의 최대공약수를 기호로 \gcd (a,b)로 표기하거나, 더 간단히 (a,b)로도 표기한다. 예를 들면,

특징[편집]

  • gcd(a, b)는 ab의 약수이다.
  • 두 수 또는 다항식의 곱은 두 수의 최대공약수와 최소공배수의 곱과 같다.
    gcd(a, b) · lcm(a, b) = a·b
  • a와 b의 최대공약수 gcd(a, b)의 값은 ax + by 꼴의 수(x, y는 정수) 중 가장 작은 양수의 값과 같다.
  • 만약 두 정수의 최대공약수가 1과 -1밖에 없는 경우, 이 두 수는 서로소라고 부른다.
  • 만약 두 다항식의 상수 이외의 최대공약수가 없을 경우, 이 두 다항식은 서로소라고 부른다.

계산법[편집]

두 수 a와 b의 최대공약수를 구하는 방법은 소인수분해를 사용하는 방법과 유클리드 호제법이 있다.

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

192=2^6 \times 3=2 \times 2 \times 2 \times 2 \times 2 \times 2 \times 3

72=2^3 \times 3^2=2 \times 2 \times 2 \times 3 \times 3

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


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


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

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

72=48 \times 1+24이다. 이와 같은 연산을 나머지가 0이 될 때까지 반복한다. 48=24 \times 2+0 나머지가 0이 되었으므로 연산을 중지한다. 이때, 나머지가 0이 되기 바로 직전의 연산에서의 나머지가 원래 두 수의 최대공약수가 된다. 이를 수식화 한 것은 호제법 문서를 참조하라.

컴퓨터 프로그래밍[편집]

나머지를 구하는 %연산을 번갈아가며 구한다.

다음은 재귀 호출을 사용한 간단한 구현이다(C/C++/C#/Java).

int gcd(int p, int q)
{
    if (q == 0) return p;
    return gcd(q, p%q);
}

다음은 재귀 호출 대신 while 루프로 대체하고 제네릭 프로그래밍을 적용한 C++ 구현이다.

#include <utility>
#include <iostream>
 
template <class _Ty>
_Ty gcd(_Ty a, _Ty b) {
	if ( a < b ) std::swap(a,b);
	while ( b > 0 ) {
		_Ty c = b;
		b = a % b;
		a = c;
	}
	return a;
}
 
int main() {
	std::cout << "gcd(2,4) = " << gcd(2,4) << std::endl;
	return 0;
}

같이 보기[편집]

외부 링크[편집]