유클리드 호제법 원리와 증명, 최소공배수까지 정리

📐 개념 정리

유클리드 호제법은 두 수의 최대공약수를 나눗셈의 나머지만 반복해서 구하는 알고리즘입니다. 원리와 증명, 계산 예시, 최소공배수로 확장하는 방법, 파이썬 구현과 활용까지 고등수학 수준에서 정리합니다.

유클리드 호제법은 두 자연수 $a$, $b$의 최대공약수를 구할 때, 큰 수를 작은 수로 나눈 나머지로 큰 수를 갈아 끼우는 일을 나머지가 0이 될 때까지 반복하는 방법입니다. 소인수분해가 필요 없고, 수가 아무리 커도 나눗셈 몇 번이면 끝나기 때문에 컴퓨터가 최대공약수를 구할 때 지금도 그대로 쓰는 알고리즘입니다.

유클리드 호제법이란 무엇인가?

호제법(互除法)이라는 이름은 "서로 나눈다"는 뜻입니다. 두 수가 번갈아 가며 나누는 수와 나뉘는 수의 역할을 바꾸기 때문에 붙은 이름이고, 기원전 300년 무렵 유클리드가 『원론』 7권에 정리했기 때문에 유클리드 호제법이라고 부릅니다. 기록으로 남아 있는 알고리즘 가운데 가장 오래된 것 중 하나입니다.

핵심은 단 하나의 등식입니다. $a$를 $b$로 나눈 나머지를 $r$이라 할 때,

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

여기서 $\gcd$는 최대공약수(greatest common divisor), $q$는 몫, $r$은 나머지입니다. 이 등식은 "$a$와 $b$의 최대공약수는 $b$와 나머지 $r$의 최대공약수와 같다"고 말합니다. 짝이 $(a, b)$에서 $(b, r)$로 바뀔 때마다 수가 작아지므로, 같은 일을 반복하면 언젠가 나머지가 0이 되고 그때 남은 나누는 수가 최대공약수입니다. 유클리드 호제법 전체가 이 등식 하나를 반복하는 것입니다.

유클리드 호제법 계산 예시 — 1071과 462

교과서에 자주 나오는 1071과 462로 유클리드 호제법을 직접 돌려 보겠습니다. 큰 수를 작은 수로 나누고, 나머지를 다음 단계의 나누는 수로 넘깁니다.

$$\begin{aligned} 1071 &= 462 \times 2 + 147 \\ 462 &= 147 \times 3 + 21 \\ 147 &= 21 \times 7 + 0 \end{aligned}$$

첫 줄에서 1071을 462로 나눈 나머지 147을 얻고, 둘째 줄에서 462를 147로 나눈 나머지 21을 얻고, 셋째 줄에서 147을 21로 나누니 나머지가 0입니다. 나머지가 0이 된 순간의 나누는 수 21이 최대공약수입니다. 실제로 $1071 = 3^2 \times 7 \times 17$, $462 = 2 \times 3 \times 7 \times 11$이므로 공통 소인수의 곱 $3 \times 7 = 21$과 일치합니다. 소인수분해로 풀면 1071이 17로 나누어떨어진다는 사실을 찾아내야 하지만, 유클리드 호제법은 나눗셈 세 번으로 끝났습니다.

나머지가 0이 되기 직전의 나머지가 답이라고 외우면 헷갈리기 쉽습니다. "나머지가 0이 된 나눗셈에서 나누는 수"라고 기억하는 편이 정확합니다. 두 수가 서로소라면 마지막 나누는 수가 1이 되어, 유클리드 호제법은 서로소 판정에도 그대로 쓰입니다.

유클리드 호제법 증명 — 왜 나머지로 바꿔도 되는가?

유클리드 호제법 증명은 "$a$와 $b$의 공약수 집합"과 "$b$와 $r$의 공약수 집합"이 완전히 같다는 것을 보이면 끝납니다. 두 집합이 같으면 그 안의 가장 큰 원소, 즉 최대공약수도 같기 때문입니다.

먼저 $d$가 $a$와 $b$의 공약수라고 합시다. $a = bq + r$을 $r = a - bq$로 고쳐 쓰면, $d$는 $a$도 나누고 $bq$도 나누므로 그 차인 $r$도 나눕니다. 따라서 $d$는 $b$와 $r$의 공약수입니다. 거꾸로 $d$가 $b$와 $r$의 공약수이면, $bq + r$은 $d$의 배수끼리의 합이므로 $a$도 $d$의 배수입니다. 따라서 $d$는 $a$와 $b$의 공약수입니다. 한쪽 공약수는 반드시 다른 쪽 공약수이므로 두 집합은 같고, $\gcd(a, b) = \gcd(b, r)$이 성립합니다.

증명에서 쓴 사실은 "약수는 합과 차에 대해 보존된다"는 것뿐입니다. 이것이 유클리드 호제법 원리의 전부이고, 나머지를 취하는 연산이 최대공약수를 전혀 건드리지 않는 이유입니다. 알고리즘이 반드시 끝난다는 것도 분명합니다. 나머지 $r$은 항상 $b$보다 작으므로 각 단계에서 두 번째 수가 엄격히 감소하고, 음이 아닌 정수는 무한히 감소할 수 없기 때문입니다.

유클리드 호제법으로 최소공배수 구하는 법

유클리드 호제법 최소공배수 문제는 별도의 알고리즘이 필요하지 않습니다. 두 자연수의 곱은 최대공약수와 최소공배수의 곱과 같다는 관계를 쓰면 됩니다.

$$\operatorname{lcm}(a,\ b) = \frac{a \times b}{\gcd(a,\ b)}$$

$\operatorname{lcm}$은 최소공배수(least common multiple)입니다. 앞의 예로 계산하면 $1071 \times 462 \div 21 = 23562$가 최소공배수입니다. 소인수분해 관점에서 보면 최대공약수는 공통 소인수를 낮은 지수로 모은 것이고 최소공배수는 높은 지수로 모은 것이라, 둘을 곱하면 각 소인수의 지수가 원래 두 수의 지수 합이 되어 $a \times b$와 같아집니다. 프로그래밍에서는 오버플로를 피하려고 $a \div \gcd(a, b)$를 먼저 계산한 뒤 $b$를 곱하는 순서를 권장합니다.

유클리드 호제법 파이썬 구현과 계산 횟수

유클리드 호제법 알고리즘은 코드로 옮기면 세 줄입니다. 파이썬에서는 나머지 연산자 %를 쓰고, 두 번째 수가 0이 될 때까지 반복합니다.

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

한 줄로 쓰면 재귀형 gcd(b, a % b)가 되고, 표준 라이브러리에는 math.gcd가 이미 들어 있습니다. C 언어도 구조는 똑같아서, 유클리드 호제법 C 구현은 while 문 안에서 임시 변수 하나로 두 값을 교환하는 형태입니다. 입력 순서를 신경 쓸 필요도 없습니다. 작은 수가 앞에 오면 첫 단계에서 $a \% b = a$가 되어 자동으로 자리가 바뀝니다.

나눗셈을 몇 번 해야 하는지도 정확히 알려져 있습니다. 라메의 정리에 따르면 유클리드 호제법의 나눗셈 횟수는 작은 수의 자릿수의 5배를 넘지 않습니다. 즉 10자리 수끼리라도 50번 안에 끝나고, 시간복잡도로는 $O(\log \min(a, b))$입니다. 가장 오래 걸리는 입력은 연속한 피보나치 수 두 개인데, 매 단계 몫이 1이라 수가 가장 천천히 줄어들기 때문입니다.

유클리드 호제법 활용 — 분수 약분에서 암호까지

가장 일상적인 유클리드 호제법 활용은 분수 약분입니다. 분자와 분모의 최대공약수로 나누면 기약분수가 되고, 계산기와 스프레드시트가 내부에서 하는 일이 바로 이것입니다. 타일 깔기 문제도 같습니다. 가로 1071, 세로 462인 직사각형을 빈틈없이 채우는 가장 큰 정사각형의 한 변은 21이고, 이 그림은 실제로 유클리드가 호제법을 설명한 방식과 같습니다. 큰 직사각형에서 정사각형을 잘라 내고 남은 작은 직사각형에 같은 일을 반복하는 것이 나눗셈의 기하학적 의미입니다.

한 단계 더 나아간 확장 유클리드 호제법은 $ax + by = \gcd(a, b)$를 만족하는 정수 $x$, $y$를 함께 찾아 줍니다. 각 단계의 나눗셈 등식을 거꾸로 거슬러 올라가 나머지를 원래 두 수의 조합으로 표현하는 방식입니다. 이 정수해가 있어야 나머지 연산에서 역원을 구할 수 있고, RSA 암호에서 개인 키를 계산하는 단계가 정확히 이 계산입니다. 우리가 매일 쓰는 인터넷 보안의 바닥에 2300년 된 유클리드 호제법이 그대로 깔려 있는 셈입니다.

저는 유클리드 호제법을 처음 배울 때 "소인수분해가 있는데 왜 이런 걸 또 배우나" 싶었습니다. 생각이 바뀐 건 대학에서 수백 자리 수의 최대공약수를 구하는 과제를 받았을 때였습니다. 소인수분해는 아예 시도조차 못 하는 크기였는데, 호제법은 나눗셈 몇백 번으로 순식간에 끝났습니다. 그때부터 이 알고리즘이 소인수분해의 대체품이 아니라, 소인수분해가 불가능한 곳에서만 작동하는 도구라는 것을 이해하게 됐습니다.

유클리드 호제법 핵심 요약

• 원리: $\gcd(a, b) = \gcd(b, a \bmod b)$. 나머지가 0이 되면 그때의 나누는 수가 최대공약수.
• 증명: 약수는 합과 차에 보존되므로 $(a, b)$와 $(b, r)$의 공약수 집합이 같다.
• 최소공배수: $a \times b \div \gcd(a, b)$로 바로 계산.
• 속도: 나눗셈 횟수는 작은 수 자릿수의 5배 이하, $O(\log n)$. 최악은 연속 피보나치 수.

함께 읽으면 좋은 글

피타고라스 정리 증명과 공식, 활용까지 완벽 정리 역행렬 구하는 방법 — 공식과 존재 조건까지 정리 유튜브 알고리즘 뜻과 원리, 추천을 결정하는 수학

참고 자료

Wikipedia — Euclidean algorithm Wolfram MathWorld — Euclidean Algorithm Python 공식 문서 — math.gcd