우선 설명하기에 앞서
2가지 개념을 먼저 이해하고 가자.
유클리드 호제법(Euclidean Algorithm)과 베주 항등식(Bezout's Identity) !
유클리드 호제법(Euclidean Algorithm)
우선 정수론에 나오는 내용이므로 여기서 나올 변수는 모두 정수라고 보면 된다.
두 정수 a, b가 있을 때 이들의 최대공약수는 gcd(a, b)로 표현한다.
a >= b일 때
a를 b로 나눈 나머지를 r이라고 하자. (0 <= r < b)
a ≡ r (mod b)
그럼 gcd(a, b) = gcd(b, r)을 만족한다.
gcd(a, b) = gcd(b, r)
왜??
a와 b의 최대공약수를 G라고 해보자.
a = αG, b = βG
α와 β는 서로소. 왜? G가 최대공약수니깐!
a를 b로 나눈 몫을 q, 나머지를 r이라고 했을 때 식으로 나타내면
a = bq + r
최대공약수 G를 통해 식을 나타내면
αG = βGq + r
r = ( βq - α )G
아하 ! r도 G의 배수, 즉 G가 r의 약수구나.
근데 gcd(b, r)이 gcd(a, b)랑 같으려면 G가 b와 r의 최대공약수여야 하네.
그 말은 즉 β와 βq - α 값이 서로소임을 보여야하는구나.
이건 귀류법을 통해 쉽게 알 수 있다.
만약 β와 βq - α 사이의 2이상의 최대공약수 p가 있다고 가정하자.
β = mp, βq - α = np
오른쪽 식에 왼쪽 β를 대입해보자.
mp - α = np
α = mp - np
α = (m - n)p
어라? 알파와 베타는 서로소인데 p라는 공약수를 갖게 된다. 따라서 가정이 모순임을 확인할 수 있다.
따라서
gcd(a, b) = gcd(b, r)
성립한다는 것을 알 수 있다.
베주 항등식(Bezout’s Identity)
적어도 둘 중 하나는 0이 아닌 정수 a,b가 있다. 그리고 a와 b의 최대공약수를 d라고 하자. 이때, 다음 세 명제가 성립한다.
1. d = ax + by 를 만족하는 정수 x, y가 반드시 존재한다.
2. d는 정수 x, y에 대하여 ax + by 형태로 표현할 수 있는 가장 작은 양의 정수다.
3. 정수 x, y에 대하여 ax + by 형태로 표현되는 모든 정수는 d의 배수이다.
해당 내용은 증명을 생략한다.
확장된 유클리드 호제법(Extended Euclidean Algorithm)
이제 위의 유클리드 호제법과 베주 항등식을 합쳐서 생각해보자.
경험상 예제를 통해 이해하는게 빠르다 !
전체적인 틀을 잡고가보자. 우리는 이제부터
r = ax + by
위와 같은 형태로 나타낼 것이다.
a = 710, b = 310이라 해보자.
a를 ax1 + by1로 나타내려면 x1 = 1, y1 = 0이다. 710 = 710 * 1 + 310 * 0
b를 ax2 + by2로 나타내면 x2 = 0, y2 = 1이다. 310 = 710 * 0 + 310 * 1
| x | y | r |
|---|---|---|
| 1 | 0 | 710 |
| 0 | 1 | 310 |
이제 r1과 r2를 나눠볼 것이다.
r1 / r2 = 710 / 310
몫은 2 나머지는 90이다. 이제 몫은 q라고 표에 추가해보면
| x | y | r | q |
|---|---|---|---|
| 1 | 0 | 710 | |
| 0 | 1 | 310 | 2 |
| 1 | -2 | 90 |
어? x3, y3은 어떻게 구했지 ?
다음 나머지를 r1 - r2 * q2로 구한 것처럼
x3 = x1 - x2 * q2
y3 = y1 - y2 * q2
그럼 이어서 더 해보자.
이번엔 r2 나누기 r3.
r2 / r3 = 310 / 90
몫은 3, 나머지는 40
| x | y | r | q |
|---|---|---|---|
| 1 | 0 | 710 | |
| 0 | 1 | 310 | 2 |
| 1 | -2 | 90 | 3 |
| -3 | 7 | 40 |
x4 = x2 - x3 * q3
x4 = 0 - 1 * 3 = -3
y4 = y2 - y3 * q3
y4 = 1 - (-2) * 3 = 7
x4, y4값이 맞나 ? 확인해보자.
710 * -3 + 310 * 7 = -2130 + 2170 = 40
맞구나. 좀 더 해보자.
r3 / r4 = 90 / 40
몫은 2, 나머지는 10
| x | y | r | q |
|---|---|---|---|
| 1 | 0 | 710 | |
| 0 | 1 | 310 | 2 |
| 1 | -2 | 90 | 3 |
| -3 | 7 | 40 | 2 |
| 7 | -16 | 10 |
마지막으로 한번만 더 해보면
| x | y | r | q |
|---|---|---|---|
| 1 | 0 | 710 | |
| 0 | 1 | 310 | 2 |
| 1 | -2 | 90 | 3 |
| -3 | 7 | 40 | 2 |
| 7 | -16 | 10 | 4 |
| -31 | 71 | 0 |
마침내 나머지가 0이 나왔다. 이러면 유클리드 호제법에서 처럼 직전 나머지인 10이 최대공약수가 된다.
gcd(710, 310) = 10
이를 구현한 간단한 파이썬 코드를 한번 살펴보자.
"""
Extended Euclidean Algorithm (Iterative version) ( a >= b )
return (x, y, r) such that a * x + b * y = r = gcd(a, b)
loop invariant :
a * x_1 + b * y_1 = r_1
a * x_2 + b * y_2 = r_2
"""
def extended_euclid(a, b):
if a == b:
return 1, 0, a
elif b == 0:
return 1, 0, a
else:
x_1 = 1
y_1 = 0
r_1 = a
x_2 = 0
y_2 = 1
r_2 = b
while r_2 != 0:
q = r_1 // r_2
r_t = r_1 - q * r_2
x_t = x_1 - q * x_2
y_t = y_1 - q * y_2
x_1, y_1, r_1 = x_2, y_2, r_2
x_2, y_2, r_2 = x_t, y_t, r_t
return x_1, y_1, r_1앞의 내용을 잘 이해했다면 코드 역시 이해가 갈 것이다.
