[알고리즘] 확장 유클리드 호제법

1. 개념

방정식의 해를 구하기 위해 사용하는 알고리즘이다. 

 

2. 원리

ax+by=c(a,b,c,x,y는 정수) 와 같은 방정식이 있을 때,

• c가 a와 b의 최대 공약수의 배수인 경우에만 정수해를 가진다. 
• ax+by=c가 정수해를 갖게 하는 c의 최솟값이 gcd(a,b)이다.

 

3. 방법

5x + 9y = 2 일때, 이 식을 만족하는 정수 x와 y를 찾아보자.

• 식이 정수해를 갖게 하는 c의 최솟값이 gcd(5,9)라는 것을 적용하여 식을 다시 놓는다.
  • 5x + 9y = 1
• 5와 9로 유클리드 호제법을 반복 실행하며 몫과 나머지를 저장한다. 나머지가 0이 되면 반복을 중단한다.

유클리드 호제법 실행	나머지	몫
5%9	5	0
9%5	4	1
5%4	1	1
4%1	0	4

• 위에서 구한 나머지와 몫을 이용하여 x와 y를 구해나간다. 이때, x = 이전 y, y = 이전 x-이전y*현재 보고 있는 몫이다.
  • 맨 처음에는 이전 x와 y가 없으니 x = 1, y = 0으로 임의 초기화를 진행한다.

나머지	몫	x, y
0	4	x=0, y=1-0*4=1
1	1	x=1, y=0-1*1=-1
4	1	x=-1, y=1-(-1)*1=2
5	0	x=2, y=-1-2*0=-1

• 맨 처음에 c를 1이라고 놓았는데, 실제 c는 2였다. 따라서 우리가 위에서 구한 x와 y에도 2배를 해줘야 한다. 따라서 답은 x=4, y=-2이다.

 

4. 관련 문제

백준 21568