확장 유클리드 알고리즘

 

확장 유클리드 호제법

• 유클리드 호제법 : 두 수의 최대 공약수 구하기
• 확장 유클리드 호제법 : 방정식의 해 구하기
•  베주 항등식 (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의 배수이기 때문에 정수해가 존재하는 것 이다.

 8x + 18y = 3 이라는 방정식은 정수해가 존재할까?
8, 4의 최대공약수는 2 이다. 하지만 우변의 3은 2의 배수가 아니다.
따라서 이는 베주 항등식에 해당되지 않으며 정수해가 존재하지 않는다.