유클리드 호제법(Euclidean Algorithm)은 두 수의 최대공약수(Greatest Common Divisor, GCD)를 구하는 고전적인 알고리즘입니다. 이 방법은 기원전 300년경 유클리드가 『원론』에서 소개했으며, 수학에서 가장 오래되었지만 여전히 효율적으로 사용되는 알고리즘 중 하나입니다.
1. 유클리드 호제법의 원리
두 정수 a, b에 대해 (단, a > b), 다음의 성질을 이용합니다: \[ \gcd(a, b) = \gcd(b, a \bmod b) \] 이 과정을 b가 0이 될 때까지 반복하면, 그때의 a가 최대공약수가 됩니다.
예를 들어, \( \gcd(48, 18) \)을 계산하면:
- 48 ÷ 18 = 2 (나머지 12)
- 18 ÷ 12 = 1 (나머지 6)
- 12 ÷ 6 = 2 (나머지 0)
따라서 최대공약수는 6입니다.
2. 알고리즘의 작동 방식
유클리드 알고리즘은 반복적으로 나머지를 계산하여 공약수를 줄여나갑니다. 시간 복잡도는 대략 \( O(\log \min(a, b)) \)이며, 매우 효율적입니다.
파이썬 구현 예시는 다음과 같습니다:
def gcd(a, b):
while b != 0:
a, b = b, a % b
return a
3. 확장 유클리드 알고리즘
확장 유클리드 알고리즘은 최대공약수뿐만 아니라 다음의 정수 x, y도 함께 구합니다: \[ ax + by = \gcd(a, b) \] 이는 모듈러 연산에서 역원을 구할 때 사용되며, RSA 암호 알고리즘 등에도 응용됩니다.
4. 응용 분야
- 분수의 기약화
- 정수론 문제 풀이
- 암호학 (RSA 등)
- 모듈러 연산 역원 계산
- 공약수 기반 알고리즘 최적화
결론
유클리드 호제법은 단순하지만 매우 강력한 수학 알고리즘입니다. 최대공약수를 빠르고 효율적으로 구할 수 있으며, 그 확장 형태는 정수론, 알고리즘, 암호 분야에서 다양하게 활용됩니다. 이 알고리즘은 수학의 기본적 개념인 ‘나눗셈’과 ‘공약수’를 깊이 이해하는 데 도움을 줍니다.