확장 유클리드 호제법 유클리드 호제법의 목적이 두 수의 최대 공약수를 구하는 것이라면 확장 유클리드 호제법의 목적은 방정식의 해를 구하는 것입니다. 제대로 이것을 이해하려면 수학적인 증명이 필요하지만 우리는 관련 알고리즘 구현만 알아봅시다. 확장 유클리드 호제법의 원리 해를 구하고자 하는 방정식은 ax + by = c 입니다. (a, b, c, x, y 는 정수) 위 방정식은 c % gcd(a,b) = 0 인 경우에만 정수해를 가집니다. 즉, c 가 a 와 b 의 최대 공약수의 배수인 경우에만 정수해를 가집니다. ax + by = c 가 정수해를 갖게 하는 c 의 최소값이 gcd(a,b) 라는 것을 의미합니다. 5x + 9y = 2 일 때 이 식을 만족하는 정수 x, y 을 구하는 과정을 봅시다. 1. ..
