Extended Euclidean

Ax + By = C

방정식의 해를 구하는 것

 

-

 

C % GCD(A, B) = 0인 경우에만 정수해를 가진다

(나누어 떨어질 때)

 

- 

 

C의 최솟값은 1임을 적용하여 중간에서 MOD 연산 시작

예제 : 5x + 9y = 2

> 5x + 9y = 1 에서 시작

 

-

 

나머지가 0이 될때까지 연산 시행

MOD	Remainder	Quotient
5 % 9 = 5	5	0
9 % 5 = 4	4	1
5 % 4 = 1	1	1
4 % 1 = 0	0	4

 

-

 

최하단에서 역순으로 올라가며 x와 y 쌍 계산

x = 이전y

y = 이전x - 이전y*Quotient

* 최하단은 이전 값이 없으므로 이전값을 (1, 0)으로 지정

 

-

 

이렇게 재귀 형식으로 구해진 최종 (x, y)는 Ax + By = GCD(A, B)를 만족

 

-

 

또한 앞에서 가정한 c = 1에다가 k 배수를 곱해주면 (kx, ky)가 방정식의 해가 됨