Extended Euclidean algorithm

Creator

Creator

Seonglae Cho

Created

Created

2024 Apr 19 6:16

Editor

Editor

Seonglae Cho

Edited

Edited

2024 Apr 19 6:20

Refs

Refs

Euclidean Algorithm

두 수 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

Extended Euclidean algorithm

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

Recommendations

////////