Seonglae Cho두 수 a와 b의 GCD 뿐만 아니라, 두 수에 대한 선형 조합에서 나오는 계수 x와 y(즉 ax+by=GCD(a, b))도 찾을 수 있습니다
- b에 대해 일반 유클리드 알고리즘을 수행하여 GCD를 찾는다
- 이 과정에서 나오는 각 단계의 나머지를 이용하여, 역순으로 x와 y의 값을 계산
- 최종적으로 x와 y를 찾아 ax+by=GCD(ab)를 만족하는 값 찾음
Extended Euclidean algorithm
In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that
https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm