확장 유클리드 호제법 유클리드 호제법 : 두 수의 최대 공약수 구하기 확장 유클리드 호제법 : 방정식의 해 구하기 베주 항등식 (Bezout's Identity) 의 명제를 기반으로 해를 구하는 알고리즘 베주 항등식 (Bezout's Identity) ax + by = d 를 만족하는 (x, y) 정수해는 d 의 값이 gcd(a, b) 의 배수일 때 존재하며, 이 존재하는 경우 나오는 값들만 (x, y) 의 정수해가 될 수 있다. 즉, d % gcd(a, b) == 0 인 경우이다. 만약 4x + 3y = 2 이라는 방적식이 있다고 하자. 이 때 (x, y)의 정수해는 ... ,(-1, 2), (2, -2), (5, -6), ... 등이 된다. 4, 3 의 최대공약수는 1이며 우변의 2는 1의 배수이기 ..