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)