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와 ..