[알고리즘 #1] 유클리드 호제법 & 확장 유클리드 호제법 쉽게 이해하기

유클리드 호제법

a 와 b의 최대공약수는 b와 (a%b)의 최대 공약수와 같다

(a>b 일 경우)

ex) 12 와 8의 최대 공약수는 12나누기 8의 나머지 값인 4와 8의 최대 공약수와 같다.

gcd(12,8) == gcd(8,12 mod 8 )

확장 유클리드 호제법

전혀 어렵지 않다. 유클리드 호제법과 유사하다.

선형 방정식 ax + by = gcd(a,b) 일 경우 x와 y의 값을 구할 수 있다.

유클리드 호제법을 적용한다.

위 식에서 gcd(a,b) == gcd(b, a%b) == gcd(a%b , b%(a%b)) ..........

이런식으로 유클리드 호제법을 적용해주게 된다.

어떻게

예를 들어 a = 300, b = 200 일 때, 300x + 200y = gcd(300, 200) 이라 하면 확장 유클리드 호제법을 적용할 수 있다.

먼저 유클리드 호제법을 적용하면

gcd(300, 200) == gcd(200, 100) == gcd(100,0) 으로 변환할 수 있다.

-> 300 = 200*1 + 100 // 몫은 1 나머지는 100

-> 200 = 100*2 +0 // 몫은 2 나머지는 0

최종 gcd(300,200) == 100 이다 .

이제는 확장 유클리드 호제법을 적용해 보면

선형 함수식 300x + 200y = gcd(300, 200) 에서

x = 1 , y = 0 이면 300*1 + 200_0 = 300

x = 0 , y = 1 이면 300*0 + 200_1 = 200 이다.

우변의 값인 gcd(300,200)을 찾기위해 우변을 300 -> 200 -> 100 으로 바꿔주며 x , y 값을 구할 수 있다.

x	y	ax+bx
1	0	300
0	1	200

==> 위에서 구한 식을 확인하면 300 = 200*1 +100 으로, ax+by 값을 100으로 바꿔 주기 위해 300 - (1*200) 즉 -1을 곱해주고 빼주면 된다.

x	y	ax+bx
1	0	300
0	1	200
1	0	100

=> x = 1 (-1*0) = 1 - 0 = 1,

=> y = 0 (-1*1) = 0 - 1 = -1

따라서 300x + 200 b = gcd(300, 200) 을 만족하는 x , y 값은 1, -1 이다.