[정수론 입문 시리즈 5편] 유클리드 호제법은 왜 최대공약수를 빠르게 구할까?

지난 글에서는 최대공약수가 두 정수의 공통 구조를 요약하는 값이라는 점을 봤습니다. 그런데 숫자가 커지면 약수를 전부 나열해서 최대공약수를 찾는 방법은 금방 불편해집니다. 이때 등장하는 강력한 도구가 유클리드 호제법입니다.

유클리드 호제법의 핵심은 복잡한 새 공식을 외우는 것이 아닙니다. 나눗셈 알고리즘으로 나온 나머지를 이용해 문제를 더 작은 문제로 바꾸는 것입니다.

What this post covers

• 유클리드 호제법의 핵심 아이디어를 설명합니다.
• 왜 $\gcd(a,b) = \gcd(b,r)$가 성립하는지 직관적으로 이해합니다.
• 두 개의 예시로 반복 계산 과정을 끝까지 추적합니다.
• 이 과정이 왜 알고리즘적 사고의 대표 예시인지 봅니다.

이번 글에서 새로 나오는 용어

• 유클리드 호제법 (Euclidean Algorithm): 나머지를 반복해서 사용해 최대공약수를 구하는 방법입니다.
• 최대공약수 (Greatest Common Divisor): 두 정수가 공통으로 가지는 약수들 가운데 가장 큰 수입니다.
• 나눗셈 알고리즘 (Division Algorithm): 정수를 몫과 나머지가 있는 표준 형태로 나타내는 정리입니다.
• 나머지 (Remainder): 나눗셈에서 남는 부분입니다.

유클리드 호제법의 핵심 아이디어

정수 $a$, $b$가 있다고 합시다. 설명을 단순하게 하기 위해 먼저 $a \ge b > 0$인 경우를 생각하겠습니다. 나눗셈 알고리즘에 의해

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

로 쓸 수 있습니다.

이때 유클리드 호제법의 핵심은 다음 문장입니다.

$$\gcd(a,b) = \gcd(b,r)$$

즉, 큰 두 수의 최대공약수 문제를 더 작은 수 $b$와 $r$의 문제로 바꿀 수 있습니다.

왜 $\gcd(a,b) = \gcd(b,r)$일까?

식

$$a = bq + r$$

를 보면

$$r = a - bq$$

입니다.

이제 어떤 수 $d$가 $a$와 $b$를 둘 다 나눈다고 해 봅시다. 그러면 $bq$도 나누고, 따라서 차이인 $r = a-bq$도 나눕니다.

반대로 어떤 수 $d$가 $b$와 $r$을 둘 다 나눈다면,

$$a = bq + r$$

도 나누게 됩니다.

즉,

• $a$와 $b$의 공약수들
• $b$와 $r$의 공약수들

가 정확히 같으므로 최대공약수도 같습니다.

핵심은 공약수 집합이 바뀌지 않는다는 점입니다.

예시 1. 48과 18의 최대공약수

먼저 48을 18로 나눕니다.

$$48 = 18 \times 2 + 12$$

따라서

$$\gcd(48,18) = \gcd(18,12)$$

입니다.

이제 18을 12로 나눕니다.

$$18 = 12 \times 1 + 6$$

따라서

$$\gcd(18,12) = \gcd(12,6)$$

입니다.

마지막으로 12를 6으로 나누면

$$12 = 6 \times 2 + 0$$

입니다. 나머지가 0이 되었으므로 계산을 멈춥니다. 이때 마지막 0이 아닌 나머지 6이 최대공약수입니다.

$$\gcd(48,18) = 6$$

예시 2. 252와 105의 최대공약수

조금 더 큰 수로 해 보겠습니다.

$$252 = 105 \times 2 + 42$$

따라서

$$\gcd(252,105) = \gcd(105,42)$$

입니다.

다음 단계는

$$105 = 42 \times 2 + 21$$

이므로

$$\gcd(105,42) = \gcd(42,21)$$

입니다.

마지막으로

$$42 = 21 \times 2 + 0$$

이므로

$$\gcd(252,105) = 21$$

입니다.

숫자는 컸지만, 나머지가 빠르게 작아지기 때문에 계산이 짧게 끝납니다.

왜 빠를까?

유클리드 호제법은 매 단계마다 문제의 크기를 줄입니다.

• 처음에는 $(a,b)$
• 다음에는 $(b,r)$

로 바뀌는데, $r$은 항상 $b$보다 작습니다. 즉, 같은 문제를 계속 반복하는 것 같지만 사실은 입력이 점점 줄어드는 구조입니다.

예를 들어 48과 18의 최대공약수를 약수 나열로 찾으려면 여러 후보를 직접 검사해야 하지만, 유클리드 호제법은

$$(48,18) \to (18,12) \to (12,6) \to (6,0)$$

처럼 몇 단계 안에 문제를 줄여 버립니다. 이 점 때문에 유클리드 호제법은 정수론뿐 아니라 알고리즘 입문에서도 자주 등장합니다. 규칙은 단순하지만, 문제를 빠르게 축소하는 좋은 예시이기 때문입니다.

Common mistakes

1. 마지막 나머지 0을 답으로 쓰는 실수

유클리드 호제법에서는 마지막 0이 아닌 나머지가 최대공약수입니다. 0이 답이 아닙니다.

2. 나누는 순서를 중간에 바꾸는 실수

항상 큰 수를 작은 수로 나누고, 그다음에는 직전의 제수와 나머지로 이어 가야 합니다. 순서가 흐트러지면 계산도 흐트러집니다.

3. 왜 맞는지 없이 절차만 외우는 실수

핵심은 $\gcd(a,b) = \gcd(b,r)$라는 원리입니다. 이 원리를 이해해야 왜 직전의 제수와 나머지로 다음 단계를 만드는지, 왜 마지막 0이 아닌 나머지가 답인지도 함께 설명할 수 있습니다.

Wrap-up

이번 글에서는 유클리드 호제법이 나눗셈 알고리즘의 나머지를 반복해서 사용해 최대공약수를 구하는 방식이라는 점을 정리했습니다. 그리고 핵심 원리인

$$\gcd(a,b) = \gcd(b,r)$$

를 통해 왜 문제를 더 작은 문제로 바꿀 수 있는지도 확인했습니다.

다음 글에서는 이 흐름을 한 걸음 더 밀어붙여, 최대공약수를 $ax + by$ 꼴과 연결하는 베주 항등식으로 이어가 보겠습니다.