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

Python의 math.gcd는 어떻게 큰 수의 최대공약수도 거의 바로 구할까요? 내부 아이디어는 생각보다 단순합니다. 나눗셈에서 나온 나머지를 계속 새 문제로 바꾸는 유클리드 호제법입니다.

약수를 전부 나열하는 방식은 작은 수에서는 괜찮지만, 숫자가 커지면 금방 불편해집니다. 유클리드 호제법의 핵심은 복잡한 새 공식을 외우는 것이 아니라, 나눗셈 알고리즘으로 나온 나머지를 이용해 문제를 더 작은 문제로 줄이는 것입니다.

What this post covers

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

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

• 유클리드 호제법 (Euclidean Algorithm): 나머지를 반복해서 사용해 최대공약수를 구하는 방법입니다.
• 최대공약수 (Greatest Common Divisor): 두 정수가 공통으로 가지는 약수들 가운데 가장 큰 수입니다.
• 나눗셈 알고리즘 (Division Algorithm): 정수를 몫과 나머지가 있는 표준 형태로 나타내는 정리입니다.
• 나머지 (Remainder): 나눗셈에서 남는 부분입니다.
• [[mathhl-m-mid-n|$m \mid n$]]: 정수 $m \ne 0$에 대해 $n=mk$를 만족하는 정수 $k$가 있을 때, "$m$이 $n$을 나눈다"고 쓰는 Silverman의 표기입니다.
• [[mathhl-m-nmid-n|$m \nmid n$]]: $m$이 $n$을 나누지 않는다는 뜻입니다.

실험: 손으로 최대공약수 찾기

먼저 표기부터 확인합시다. Silverman은 정수 $m \ne 0$에 대해 $n$이 $m$의 배수이면, 즉 어떤 정수 $k$가 있어서

$n=mk$

이면 "$m$이 $n$을 나눈다"고 말하고

$m \mid n$

이라고 씁니다. 예를 들어 $6=3\cdot2$, $133=19\cdot7$이므로 $3\mid6$, $19\mid133$입니다. 반대로 나누지 않으면 $m\nmid n$이라고 씁니다. 예를 들어 $5\nmid7$입니다.

이제 종이와 연필만으로 다음 문제를 풀어 보겠습니다.

문제 1: 12와 20의 최대공약수를 구하시오.

• 12의 약수: 1, 2, 3, 4, 6, 12
• 20의 약수: 1, 2, 4, 5, 10, 20
• 공통 약수: 1, 2, 4
• 최대공약수: 4

문제 2: 18과 30의 최대공약수를 구하시오.

• 18의 약수: 1, 2, 3, 6, 9, 18
• 30의 약수: 1, 2, 3, 5, 6, 10, 15, 30
• 공통 약수: 1, 2, 3, 6
• 최대공약수: 6

약수를 모두 나열하는 방법은 작은 수에서는 잘 작동합니다. 하지만 숫자가 커지면 꽤 번거롭습니다. Silverman도 $\gcd(225,120)=15$는 $225=3^2\cdot5^2$, $120=2^3\cdot3\cdot5$처럼 인수분해로 확인할 수 있지만, 일반적으로 인수분해가 최대공약수를 구하는 효율적인 방법은 아니라고 지적합니다. 더 빠른 방법이 없을까요?

패턴 발견: 나머지의 힘

이번에는 나눗셈을 이용해 봅시다. 책의 첫 번째 유클리드 호제법 예시는 $\gcd(132,36)$입니다.

먼저 132를 36으로 나누면 몫이 3이고 나머지가 24입니다.

$132 = 3 \times 36 + 24$

다음으로 36을 앞에서 얻은 나머지 24로 나눕니다.

$36 = 1 \times 24 + 12$

다음으로 24를 12로 나누면 나머지가 0이 됩니다.

$24 = 2 \times 12 + 0$

유클리드 호제법은 나머지가 0이 되는 나눗셈을 하기 바로 전 단계의 나머지로 최대공약수를 찾는 방법입니다. 따라서

$\gcd(132,36)=12$

입니다.

왜 이런 일이 가능할까요? 첫 줄 $132=3\times36+24$를 보면, 132와 36을 모두 나누는 수는 $24=132-3\times36$도 나눕니다. 반대로 36과 24를 모두 나누는 수는 $132=3\times36+24$도 나눕니다. 그래서 132와 36의 공약수 = 36과 24의 공약수입니다. 같은 이유로 36과 24의 공약수 = 24와 12의 공약수입니다.

이론 정리: 유클리드 호제법

정수 $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. 132와 36의 최대공약수

책의 계산을 다시 한 줄씩 정리하면 다음과 같습니다.

$132 = 3 \times 36 + 24$

따라서

$\gcd(132,36)=\gcd(36,24)$

입니다.

다음 단계는

$36 = 1 \times 24 + 12$

이므로

$\gcd(36,24)=\gcd(24,12)$

입니다.

마지막으로

$24 = 2 \times 12 + 0$

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

$\gcd(132,36)=12$

예시 2. 큰 수의 최대공약수

Silverman은 유클리드 호제법이 인수분해보다 훨씬 효과적이라는 점을 보여 주기 위해 큰 수 예시를 듭니다.

$\gcd(1160718174,316258250)$

을 계산해 봅시다.

$\begin{aligned} 1160718174 &= 3 \times 316258250 + 211943424 \\ 316258250 &= 1 \times 211943424 + 104314826 \\ 211943424 &= 2 \times 104314826 + 3313772 \\ 104314826 &= 31 \times 3313772 + 1587894 \\ 3313772 &= 2 \times 1587894 + 137984 \\ 1587894 &= 11 \times 137984 + 70070 \\ 137984 &= 1 \times 70070 + 67914 \\ 70070 &= 1 \times 67914 + 2156 \\ 67914 &= 31 \times 2156 + 1078 \\ 2156 &= 2 \times 1078 + 0 \end{aligned}$

따라서 마지막 0이 아닌 나머지는 1078이고,

$\gcd(1160718174,316258250)=1078$

입니다. 실제로

$1160718174=1078\times1076733, \qquad 316258250=1078\times293375$

이므로 1078이 두 수의 공약수임도 바로 확인할 수 있습니다.

왜 빠를까?

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

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

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

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

$(132,36) \to (36,24) \to (24,12) \to (12,0)$

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

Python으로 확인하기

손으로 한 유클리드 호제법은 그대로 짧은 코드로 옮길 수 있습니다. 핵심은 $(a,b)$를 계속 $(b, a \bmod b)$로 바꾸는 것입니다.

def gcd_euclid(a, b):
    steps = []
    while b != 0:
        q = a // b
        r = a % b
        steps.append((a, b, q, r))
        a, b = b, r
    return a, steps

for a, b in [(132, 36), (1160718174, 316258250)]:
    g, steps = gcd_euclid(a, b)
    print(f"gcd({a}, {b}) = {g}")
    for old_a, old_b, q, r in steps:
        print(f"  {old_a} = {old_b} × {q} + {r}")
    print()

출력되는 나눗셈 줄을 손계산과 비교해 보세요. $132,36$에서는 마지막 0이 아닌 나머지가 12이고, $1160718174,316258250$에서는 1078입니다.

Python에는 math.gcd도 있지만, 처음 배울 때는 위처럼 직접 구현해 보는 것이 좋습니다. 그래야 “왜 답이 나오는가”가 코드 속에서도 보입니다.

Common mistakes

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

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

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

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

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

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

연습 문제

Silverman의 연습 문제와 연결해서 공부하려면 다음을 특히 확인해 보세요.

• 연습 문제 5.1: 유클리드 호제법을 이용해 $\gcd(12345,67890)$, $\gcd(54321,9876)$을 구하는 문제입니다.
• 연습 문제 5.4: 최소공배수 $\operatorname{LCM}(m,n)$을 정의하고, $m$, $n$, $\gcd(m,n)$ 사이의 관계를 찾는 문제입니다.

아래 점검 퀴즈에서도 유클리드 호제법을 직접 적용해 보세요.

Wrap-up

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

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

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

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