확장된 유클리드 알고리즘(extended euclidean algorithm) 구현해보면서 익히기

1. 베주 항등식(Bézout's Identity) 적어도 하나가 0이 아닌 두 정수 a,b에 대하여 $$ax+by = gcd(a,b)$$ 를 만족하는 정수해 x,y가 반드시 존재한다. 여기서 정수해 x,y는 유일하지 않다. 왜냐하면, 양변에 ab를 더하고 빼보면 $$ax+ab + by-ab = gcd(a,b)$$ 이므로, $$a(x+b) + b(y-a) = gcd(a,b)$$ 이므로, (x,y)가 정수해라면, (x+b,y-a)도 정수해가 된다. 2. 유클리드 알고리즘(Euclidean algorithm) 최대공약수를 빠르게 구하는 알고리즘 - 유클리드 호제법 (tistory.com) 최대공약수를 빠르게 구하는 알고리즘 - 유클리드 호제법 1. 최대공약수 두 자연수 a,b가 공통으로 가지는 약수중에서 가장 큰..