이 글에서는 두 수의 최대공약수(GCD)를 구하는 문제를 확장 유클리드 호제법(Extended Euclidean Algorithm)으로 해결하는 파이썬 프로그램을 살펴봅니다.
문제 정의
두 개의 수가 주어졌을 때, 이 두 수의 최대공약수(GCD)를 계산하여 화면에 출력하는 것이 목표입니다.
최대공약수와 유클리드 호제법의 원리
두 수의 최대공약수(GCD, Greatest Common Divisor)란 두 수를 모두 나누어 떨어지게 하는 가장 큰 정수를 의미합니다. 기본적인 유클리드 호제법은 다음 원리를 이용합니다.
- gcd(a, b) = gcd(b % a, a)
- 나머지가 0이 되는 순간의 값이 곧 최대공약수
확장 유클리드 알고리즘은 여기서 한 단계 더 나아가, 재귀 호출 과정에서 얻어진 이전 값을 활용해 다음 조건을 만족하는 정수 x와 y까지 함께 구해줍니다.
a × x + b × y = gcd(a, b)
이 성질 덕분에 확장 유클리드 알고리즘은 모듈러 역원(modular inverse) 계산, RSA 암호화 등 정수론과 암호학 분야에서 널리 활용됩니다.
구현 예제
# 확장 유클리드 알고리즘
def gcdExtended(a, b, x, y):
# 기저 사례(Base Case)
if a == 0:
x = 0
y = 1
return b
x1 = 1
y1 = 1 # 결과 저장용
gcd = gcdExtended(b % a, a, x1, y1)
# 이전에 계산된 값으로 x, y 갱신
x = y1 - (b // a) * x1
y = x1
return gcd
x = 1
y = 1
a = 11
b = 15
g = gcdExtended(a, b, x, y)
print("gcd of", a, "&", b, "is =", g)
참고: 파이썬 3에서는 나눗셈 연산자 /가 실수(float) 결과를 반환하므로, 몫을 구할 때는 반드시 정수 나눗셈 연산자 //를 사용해야 올바른 결과를 얻을 수 있습니다.
실행 결과
gcd of 11 & 15 is = 1
11과 15는 서로소(coprime) 관계이므로 최대공약수가 1로 출력됩니다. 또한 이 경우 11 × x + 15 × y = 1을 만족하는 정수 쌍 (x, y) 역시 함께 구할 수 있습니다.
동작 원리 요약
- 재귀 호출을 통해 a가 0이 될 때까지 나눗셈을 반복합니다.
- 기저 사례에서 x = 0, y = 1을 설정하고 b를 반환합니다.
- 재귀가 되돌아오면서 공식 x = y₁ − (b ÷ a) × x₁, y = x₁을 이용해 계수를 갱신합니다.
- 모든 호출이 종료되면 gcd와 함께 베주 계수(Bézout coefficients)가 완성됩니다.
마무리
이번 글에서는 파이썬으로 확장 유클리드 알고리즘을 구현하는 방법을 배웠습니다. 단순히 최대공약수만 구하는 것이 아니라, ax + by = gcd(a, b) 형태의 선형 결합 계수까지 구할 수 있다는 점이 일반 유클리드 호제법과의 가장 큰 차이입니다. 모듈러 역원 계산이나 암호학 알고리즘 구현에 꼭 필요한 개념이니, 코드를 직접 실행하며 동작 과정을 익혀보시길 권합니다.