확장 유클리드 호제법

이전에 유클리드 호제법에 대해 알아본 적이 있었습니다. 유클리드 호제법과 확장 유클리드 호제법 모두 정수론을 이용한 알고리즘인데요, 유클리드 호제법이 a와 b의 최대 공약수 gcd(a, b)를 구하는 알고리즘이었다면, 확장 유클리드 호제법은 더 나아가 a와 b의 최대 공약수 gcd(a, b)와 ax+by = gcd(a, b)를 만족하는 x, y까지 구하는 알고리즘 입니다.

 

 

그럼 확장 유클리드 호제법을 어떻게 사용하는지 알아보겠습니다.

확장 유클리드 호제법을 사용하기 위해 간단한 규칙을 먼저 살펴봐야 합니다. 아래 규칙을 통해서 Ri가 0이 될 때까지 반복했을 때 마지막으로 나온 Xi, Yi가 gcd(a, b)를 만족하는 x, y가 됩니다.

 

 

초기 설정해줘야 하는 값은 X0 = 1, X1 = 0, Y0 = 0, Y1 = 1 입니다. 이때, Ri는 a * Xi + b * Yi 의 값입니다.

그렇게 초기 설정을 해주고 나면, 아래와 같은 표를 만들 수 있습니다.

 

 

 

 

좀 더 이해를 쉽게 하기 위해 예시를 들어볼까요? 이 확장 유클리드 호제법을 통해 210x + 66y = gcd(210, 66) 인 x와 y 값을 찾아보겠습니다.

 

먼저 처음 초기값은 아래와 같은 표가 됩니다.

 

 

그럼 이제, Ri의 값이 0이 나올 때까지 위에서 말한 규칙을 반복합니다.

 

 

 

이제 Ri가 0이 되었죠? 그럼 여기서 나온 마지막 X3 와 Y3를 210x + 66y에 대입하면 R3 값인 6이 gcd(210, 66)으로 나오게 됩니다!

 

210*(-5) + 66*16 = -1050 + 1056 = 6

따라서 gcd(210, 66) = 6

 

이렇게 말이죠. 그럼 우린 gcd(a, b) 값과 함께 ax+by = gcd(a, b) 를 만족하는 x와 y값도 찾았습니다.

확장 유클리드 호제법의 규칙만 알면 구하는 방법은 어렵지 않죠? :)