Expanded Euclid's Algorithm - 확장된 유클리드 호제법
서론
아직은 이걸 왜 알아야하는지 모르겠지만 일단 하는 공부 ㅋ
확장 유클리드 호제법 공식을 처음 봤을때 최소공배수인가라는 생각을 했고,
퇴근하며 운전하는 동안 머릿속으로 알고리즘을 짜놨는데 아니었음 ㅋㅋㅋ
근데 뭐 원리는 거의 같으니...
이론
베주 항등식
베주 항등식에 대해서 알아보자.
확장된 유클리드 호제법에 대한 글인줄 알았는데 무슨 소리냐고?
이게 곧 확장된 유클리드 호제법이랑 연결된다.
베주 항등식이란
두 자연수의 최대 공약수를 그 두 수의 배수의 합으로 나타낼 수 있다.
라는 것이다.
이건 또 무슨 소리냐고?
식으로 보면 이해하기 쉽다.
a, b의 최대 공약수는 GCD(a, b)로 표현할 수 있다.
이를 베주 항등식과 연계해서 표현해보면
ax + by = GCD(a,b)
를 만족하는 식을 베주 항등식이라고 한다.
베주 항등식은 곧 정수 해가 존재하는 식을 이야기한다.
다시 이야기하자면, 예를 들어
12x + 3y = 3
이라는 방정식이 있다고 가정하자.
이 때 x와 y는 (1,-3), (2,-7), ... , (-1,5), (-2,9) ... 와 같이 무수히 많은 해를 가지게 된다.
하지만
12x + 3y = 2
라는 방정식은 정수해가 존재하지 않는다.
이를 빠르게 판단할 수 있는 방법이 12 mod 3의 해가 2의 배수인지 확인하는 것이다.
만일 배수라면 정수해가 존재하고, 아니라면 존재하지 않는다.
그럼 여기서 x와 y는 어떻게 구할 수 있을까.
예를 들어
a = 15
b = 9
라고 가정하자.
GCD(15,9) = 3이므로
이를 베주 방정식에 넣어보면
15x + 9y = 3
이 된다.
여기서 x와 y를 구하려면 초기값을 두고,
결과값이 양수냐 음수냐에 따라 x 또는 y에 1씩 더하거나 빼면서 계산하면 될 것이다.
즉 아래 테이블과 같다.
x가 양수, y가 음수일 때
| x | y | ax | by | ax + by |
| 1 | 0 | 15 | 0 | 15 |
| 1 | -1 | 15 | -9 | 6 |
| 1 | -2 | 15 | -18 | -3 |
| 2 | -2 | 30 | -18 | 12 |
| 2 | -3 | 30 | -27 | 3 |
| 2 | -4 | 30 | -36 | -6 |
| 3 | -4 | 45 | -36 | 9 |
| 3 | -5 | 45 | -45 | 0 |
| 4 | -5 | 60 | -45 | 15 |
| 4 | -6 | 60 | -54 | 6 |
| 4 | -7 | 60 | -63 | -3 |
| 5 | -7 | 75 | -63 | 12 |
| 5 | -8 | 75 | -72 | 3 |
| ... | ||||
x가 음수, y가 양수일 때
| x | y | ax | by | ax + by |
| 0 | 1 | 0 | 9 | 9 |
| -1 | 1 | -15 | 9 | -6 |
| -1 | 2 | -15 | 18 | 3 |
| ... | ||||
이외에도 무수히 많은 해를 구할 수 있겠지만, 둘의 최솟값만 구하면 (2, -3), (-1, 2) 가 된다.
즉,
s가 양수이고 t가 음수인
그리고
s가 음수이고 t가 양수인
두가지 답을 구할 수 있다.
확장된 유클리드 호제법
이제 확장된 유클리드 호제법을 알아보자.
간단히 이야기하면 유클리드 호제법의 역 연산이다.
위의
GCD(15,9)
를 유클리드 호제법으로 다시 계산해보면 아래와 같아진다.
15 = 9 x 1 + 6
9 = 6 x 1 + 3
6 = 3 x 2
GCD(15,9) = 3
이를 다시 역산해보면 아래와 같다.
3 = 9 - 6
= 9 - (15 - 9 x 1)
= 9 - 15 + 9 x 1
이를 다시 정리해보면
= 15 x (-1) + 9 x (1 + 1)
가 되기 때문에 x와 y는 (-1, 2)가 된다.
보통은 as + bt = r의 꼴로 표현하기에
15 x -1 + 9 x 2 = 3
이 되며
a = 15, s = -1, b = 9, t = 2, r = 3
이 되는 것이다.
a와 b 두 자연수가 서로소인 경우
확장된 유클리드 호제법에서 두 자연수가 서로소인 경우에
구해진 값 s가 만일 음수라면 b를 더해주면 양수로 만들 수 있다.
다시 생각해도 빡치는데,
많은 글들이 냅다 s에 b를 더하면 양수를 만들 수 있다고만 적어놔서 왜 그런지 한참 생각했다 -_-
전제 조건은 두 자연수가 서로소인 경우, 즉 GCD(a ,b) = 1인 경우이다.
예를 들어
7s + 5t = GCD(7,5)
7s + 5t = 1
이고, 구해진 s와 t는 각각
(3, -4), (-2, 3)
이다.
이 때 음수 s인 -2와 b인 5를 더하면 양수 케이스인 3이 나온다.
더불어 음수 t인 -4와 a인 7을 더하면 양수 케이스인 3이 나온다.
다시 표현하자면 두 s를 빼면 b가 나오고, 두 t를 빼면 a가 나온다.
또 다시 표현하자면 두 s의 절대값을 더하면 b고, 두 t의 절대값을 더하면 a다.
즉, 둘 중 한가지 케이스만 구해도 두 케이스 모두 쉽게 계산할 수 있게 된다.
소스코드
위에서 table로 구한 것을 소스코드로 작성해보았다.
(확장된 유클리드 호제법 방식으로의 계산은 나중에 추가하는 것으로...)
a = int(input())
a_s = a
b = int(input())
b_t = b
if a < b:
a,b = b,a
a_s, b_t = b,a
while 1:
r = a % b
if r == 0:
GCD = b
break
a,b = b,r
print('GCD = ', GCD)
r = 0
s = 1
t = -1
while GCD != r:
r = a_s * s + b_t * t
if GCD == r:
break
if r > 0:
t -= 1
else:
s += 1
print('s = ',s,'t = ',t)
r = 0
s = -1
t = 1
while GCD != r:
r = a_s * s + b_t * t
if GCD == r:
break
if r < 0:
t += 1
else:
s -= 1
print('s = ',s,'t = ',t)