유클리드 호제법

유클리드 호제법(Euclidean algorithm)은 두 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘이다. '호제법(互除法)'이란 두 수가 서로(互) 상대방을 나누어(除) 결국 원하는 수를 얻는다는 뜻에서 유래했다. 2개의 자연수 $a, b$ 에 대하여 $a$ 를 $b$ 로 나눈 나머지를 $r$ 이라 하면, $a$ 와 $b$ 의 최대공약수는 $b$ 와 $r$ 의 최대공약수와 같다는 성질을 이용한다. 이 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 곧 최대공약수이다.

배너 광고

개요 및 어원

유클리드 호제법은 두 수의 최대공약수를 효율적으로 구하는 방법이다. '호제법'이라는 용어 외에 두 정수를 연속적으로 나눈다는 의미에서 **연제법(連除法)**이라고도 부른다. 일반적으로 숫자가 커질수록 소인수분해를 통해 최대공약수를 찾기 어려워지는데, 호제법을 이용하면 큰 수의 계산도 비교적 빠르게 수행할 수 있다.

역사적 배경

이 알고리즘은 기원전 300년경 고대 그리스의 수학자 유클리드가 집필한 《원론》 제7권(명제 1~3)과 제10권에 명시적으로 기술되어 있다. 이는 인류 역사상 가장 오래된 알고리즘으로 평가받는다. 다만 유클리드가 이를 처음 발견한 것은 아니며, 그 이전인 기원전 375년경 에우독소스나 피타고라스 학파에서 이미 사용하던 정수론 지식을 유클리드가 정리하여 기록한 것으로 추정된다.

알고리즘 원리

두 양의 정수 $a, b$ ( $a > b$ )에 대하여 다음과 같은 정리가 성립한다.

$a = bq + r \quad (0 \le r < b)$

이때 $a$ 와 $b$ 의 최대공약수는 $b$ 와 $r$ 의 최대공약수와 같다. 즉, $\gcd(a, b) = \gcd(b, r)$ 이다. 이 과정을 나머지가 0이 될 때까지 반복하면 마지막에 나누는 수가 최대공약수가 된다.

증명

$\gcd(a, b) = G$ 라 하면, $a = GA, b = GB$ (단, $A, B$ 는 서로소)로 나타낼 수 있다. 이를 $r = a - bq$ 에 대입하면 $r = GA - GBq = G(A - Bq)$ 가 된다. 따라서 $G$ 는 $r$ 의 약수이기도 하므로 $b$ 와 $r$ 의 공약수이다. 이때 $B$ 와 $A - Bq$ 가 서로소임을 증명하면 $G$ 가 $b$ 와 $r$ 의 최대공약수임이 확정된다.

계산 예시

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

1071을 1029로 나누면 나머지는 42이다. ( $1071 = 1029 \times 1 + 42$ )
1029를 42로 나누면 나머지는 21이다. ( $1029 = 42 \times 24 + 21$ )
42를 21로 나누면 나머지는 0이다. ( $42 = 21 \times 2 + 0$ )

나머지가 0이 되었을 때 나누는 수인 21이 1071과 1029의 최대공약수이다.

프로그래밍 구현

현대 컴퓨터 과학에서 유클리드 호제법은 재귀 함수나 반복문을 통해 간단히 구현된다.

방식	Python 예시 코드
반복문	`def gcd(a, b): while b: a, b = b, a % b; return a`
재귀	`def gcd(a, b): return a if b == 0 else gcd(b, a % b)`

응용 및 확장

유클리드 호제법은 단순히 최대공약수를 구하는 것 이상의 용도로 활용된다.

최소공배수(LCM): 두 수 $a, b$ 의 곱을 최대공약수로 나누면 최소공배수를 얻을 수 있다. ( $LCM(a, b) = (a \times b) / GCD(a, b)$ )
서로소 판별: 최대공약수가 1이면 두 수는 서로소이다.
확장 유클리드 알고리즘: $ax + by = \gcd(a, b)$ 를 만족하는 정수 $x, y$ 를 찾는 데 사용되며, 이는 암호학(RSA 등)에서 모듈러 역수를 구하는 데 필수적이다.
기약분수: 분자와 분모를 최대공약수로 나누어 분수를 단순화할 수 있다.

참고 자료

5건