확장 유클리드 호제법 (Extended Euclidean Algorithm)
1. 정의 확장 유클리드 호제법은 두 정수 $a, b$에 대해 $GCD(a, b) = d$라고 했을 때, $ax + by = d$를 만족하는 $x, y$를 찾을 때 이용되는 알고리즘이다. 확장 유클리드 호제법에 대해 공부하기 전에 유클리드 호제법과 베주 항등식이 무엇인지 먼저 알아보자. 1) 유클리드 호제법 두 정수 $a, b$에 대하여 최대공약수 $GCD(a, b)$를 빠르게 찾는 알고리즘이다. $a$를 $b$로 나눈 나머지를 $r$이라고 할 때, $GCD(a, b) = GCD(b, r)$이 성립하는데 유클리드 호제법은 이 성질을 이용한다. 아래와 같이 한 숫자에서 다른 숫자를 계속 나누어서 나머지가 0이 될 때까지 위 성질을 이용하면 몇 번의 연산만으로 $GCD(a, b)$를 구할 수 있다. $a$를..
