최대공약수

소인수분해를 이용한 최대공약수 계산 방법은 각 수를 소인수분해한 후, 공통된 소인수들만을 곱하여 구하는 방식이다. 이 방법은 정수의 인수 구조를 명확히 보여준다는 장점이 있지만, 큰 수를 소인수분해하는 데 어려움이 있을 수 있다.

구체적인 절차는 다음과 같다. 먼저, 주어진 두 정수 a와 b를 각각 소인수분해하여 소인수들의 곱으로 표현한다. 예를 들어, a = 2^3 * 3^2 * 5, b = 2^2 * 3^4 * 7로 분해되었다고 가정하자. 다음으로, 두 분해식에서 공통으로 나타나는 소인수들, 즉 2와 3을 찾는다. 마지막으로, 각 공통 소인수에 대해 두 수의 분해식에서 그 지수가 더 작은 값을 선택하여 곱한다. 이 예에서는 소인수 2의 지수는 3과 2 중 작은 값인 2를, 소인수 3의 지수는 2와 4 중 작은 값인 2를 선택한다. 따라서 최대공약수 gcd(a, b)는 2^2 * 3^2, 즉 36이 된다.

이 방법은 세 수 이상의 최대공약수를 구할 때도 동일한 원리로 확장 적용할 수 있다. 모든 수의 소인수분해 결과에서 공통적으로 등장하는 소인수들만을 취하고, 각 소인수에 대해 모든 수의 지수 중 가장 작은 값을 선택하여 곱하면 된다. 이 접근법은 최대공약수의 정의, 즉 공통 약수 중 가장 큰 수라는 개념을 소인수 분해를 통해 시각적으로 구현한 것이다.

그러나 이 방법은 소인수분해 자체가 큰 수에 대해 계산적으로 복잡할 수 있다는 한계를 지닌다. 이러한 경우에는 유클리드 호제법이 더 효율적인 대안이 된다.

유클리드 호제법은 두 정수의 최대공약수를 구하는 효율적인 알고리즘이다. 기원전 3세기 경 유클리드의 저서 《원론》에 기록된 고전적인 방법으로, 나눗셈과 나머지를 반복적으로 활용하는 것이 특징이다. 이 방법은 두 수가 매우 클 때, 소인수분해를 이용하는 방법보다 훨씬 빠르고 실용적이다.

알고리즘의 핵심 원리는 다음과 같다. 두 정수 a와 b (a > b)가 있을 때, a를 b로 나눈 나머지를 r이라고 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다는 성질, 즉 gcd(a, b) = gcd(b, r)을 이용한다. 이 과정을 나머지가 0이 될 때까지 반복하며, 나머지가 0이 되는 순간의 나누는 수가 바로 두 수의 최대공약수가 된다.

예를 들어, 1071과 1029의 최대공약수를 구하는 과정은 다음과 같다.

세 번째 단계에서 나머지가 0이 되었으므로, 최대공약수는 이때의 나누는 수인 21이다. 이 알고리즘은 컴퓨터 과학과 정수론에서 기초적인 도구로 널리 사용되며, 확장 유클리드 호제법으로 발전하여 모듈러 역원 계산이나 디오판토스 방정식 해결 등에도 응용된다.

두 정수 a와 b의 최대공약수와 최소공배수는 밀접한 관계를 가진다. 두 수의 최대공약수를 G, 최소공배수를 L이라 할 때, 두 수 a와 b는 각각 G와 서로소인 두 정수 m, n을 사용하여 a = Gm, b = Gn으로 표현할 수 있다. 이때 m과 n은 서로소 관계이다.

이 표현을 이용하면 두 수의 곱 a × b는 G × G × m × n이 되며, 최소공배수 L은 G × m × n이 된다. 따라서 a와 b의 곱은 최대공약수와 최소공배수의 곱과 같다는 중요한 공식이 성립한다. 즉, a × b = G × L 또는 L = (a × b) / G 라는 관계가 항상 성립한다.

이 관계는 분수의 덧셈이나 뺄셈 시 통분을 할 때 유용하게 활용된다. 두 분수의 분모가 각각 a와 b일 때, 두 분수의 공통분모는 최소공배수 L이 되어야 하며, 이 L은 두 분모의 곱을 최대공약수로 나눈 값으로 쉽게 구할 수 있다. 또한 세 수 이상의 최대공약수와 최소공배수를 구할 때도, 두 수씩 짝지어 이 관계를 반복적으로 적용하는 방법을 사용할 수 있다.

분수를 약분한다는 것은 분자와 분모를 그들의 공통된 약수로 나누어 더 간단한 형태, 즉 기약분수로 만드는 과정이다. 이때 사용되는 공통 약수는 분자와 분모의 약수이며, 특히 최대공약수로 나누면 한 번의 연산으로 분수를 완전히 약분할 수 있다.

예를 들어, 분수 24/36을 약분하려면 먼저 분자 24와 분모 36의 최대공약수를 구한다. 두 수의 최대공약수는 12이므로, 분자와 분모를 각각 12로 나누면 2/3이 된다. 이 결과인 2/3은 분자와 분모가 서로소인 기약분수이다. 이처럼 최대공약수를 활용한 약분은 분수를 가장 효율적으로 간단히 만드는 방법이다.

분수의 약분은 산수와 초등수학 교육에서 기본적으로 다루어지며, 유리수의 연산을 수행할 때 필수적인 전처리 과정이다. 또한, 비율을 간단히 표현하거나, 확률 계산, 공학 문제에서 수치를 단순화하는 등 다양한 응용수학 분야에서 널리 사용된다.

세 수 이상의 정수에 대한 최대공약수는 그 모든 수의 공통 약수 중 가장 큰 수를 의미한다. 예를 들어, 12, 18, 24의 최대공약수는 이 세 수를 모두 나누는 가장 큰 정수인 6이다. 이를 표기할 때는 gcd(12, 18, 24) = 6과 같이 나타낸다.

세 수 이상의 최대공약수를 구하는 기본적인 방법은 두 수의 최대공약수를 반복적으로 적용하는 것이다. 즉, gcd(a, b, c)의 값은 먼저 두 수 a와 b의 최대공약수를 구한 후, 그 결과와 나머지 수 c의 최대공약수를 다시 구하는 것과 같다. 이는 결합 법칙과 유사한 성질로, 수학적으로 gcd(a, b, c) = gcd(gcd(a, b), c)로 표현된다. 이 방법을 확장하면 네 개, 다섯 개 이상의 수에 대해서도 순차적으로 계산할 수 있다.

실제 계산에는 소인수분해나 유클리드 호제법을 활용한다. 유클리드 호제법을 사용할 경우, 먼저 임의의 두 수에 대해 알고리즘을 적용해 최대공약수를 구하고, 그 결과와 다음 수에 대해 같은 과정을 반복한다. 예를 들어, 18, 24, 36의 최대공약수를 구하려면, 먼저 gcd(18, 24)=6을 구한 후, 다시 gcd(6, 36)=6을 계산하여 최종 결과 6을 얻는다.

이 개념은 여러 수가 공통으로 나누어떨어지는 가장 큰 수를 찾는 문제, 예를 들어 여러 길이의 막대를 동일한 길이로 나누거나, 여러 분모를 가진 분수의 연산을 간단히 하는 등 실생활과 수학 문제 해결에 널리 응용된다. 또한, 모든 수의 최대공약수가 1인 경우, 그 수들을 '쌍마다 서로소'가 아닐 수 있지만, 집합적으로 서로소 관계에 있다고 말할 수 있다.