최대공약수

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

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

특징[편집]

  • 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의 최대공약수를 소인수 분해를 이용하여 구하여 보자. 일단 두 수를 소인수 분해한다.

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


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


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

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

이다. 이와 같은 연산을 나머지가 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;
}

같이 보기[편집]

외부 링크[편집]