확장된 유클리드 호제법 (gcd)

이전의 유클리드 호제법으로 최대공약수를 구하는법을 알았다

유클리드 호제법 이론 (최대 공약수 구하기)

더 나아가서 이를 이용해서

a, b의 최대공약수와 함께 이 최대공약수가 되기위해서

a에 몇을 곱하고 b에 몇을 곱해야하는지 구해보자

gcd(a,b) = a * x + b * y

이러한 형식으로 표현되는데 x와 y를 구하는것이다

 

이전의 78696과 19332의 경우로 확장된 유클리드 호제법을 사용해 보겠다

78696 = 19332 * 4 + 1368

    1368 = 78696 + 19332(-4) ...(i)

19332 = 1368 * 14 + 180

    180 = 19332 + 1368(-14)

    180 = 19332 + (i)(-14)

    180 = 19332 -14(78696 + 19332(-4))

    180 = 78696 *(-14) + 19332 * 57 ...(ii) 

1368 = 180 * 7 + 108

    108 = 1368 + 180(-7)

    108 = (i) -7(ii)

    108 = 78696 + 19332(-4) -7(78696 *(-14) + 19332 * 57)

    108 = 78696 * 99 + 19332 * (-403) ...(iii)

180 = 108 * 1 + 72

    72 = 180 + 108(-1)

    72 = (ii) -(iii)

    72 = 78696 * (-14) + 19332 * 57 -(78696 * 99 + 19332 * (-403))

    72 = 78696 * (-113) + 19332 * 460 ...(iiii)

108 = 72 * 1 + 36

    36 = 108 + 72(-1)

    36 = (iii) -(iiii)

    36 = (78696 * 99 + 19332 * (-403)) -(78696 * (-113) + 19332 * 460)

    36 = 78696 * 212 + 19332 * (-863)

72 = 36 * 2 + 0

 

최대공약수는 36으로 동일하며

x = 212

y = -863 이다

 

용도

- 중국인의 나머지 정리

- 디오판토스 방정식

- 합동식 (Congruence Equation) 의 계산

 

코드

function EEA(a, b) {
  let [r1, r2, s1, s2, t1, t2, q, r, s, t] = [a, b, 1, 0, 0, 1, 0, 0, 0, 0];
  while (true) {
    q = parseInt(r1 / r2);
    r = r1 - q * r2;
    s = s1 - q * s2;
    t = t1 - q * t2;
    if (r === 0) {
      console.log(`최대공약수 : ${r2}, x : ${s2}, y : ${t2}`);
      break;
    }
    r1 = r2;
    r2 = r;
    s1 = s2;
    s2 = s;
    t1 = t2;
    t2 = t;
  }
}

 

참고

[알고리즘] 확장된 유클리드 알고리즘 (Extended Euclidean Algorithm) 으로 최대공약수 (GCD) 구하기 (C++로