just studying

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

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

즉, a, b의 최대공약수와 b, r의 최대공약수가 같음을 이용해서 최대공약수를 빠르게 구하는 방법이다. 예를들어 78696과 19323의 최대 공약수를 구하고자 한다면 78696 = 19323 * 4 + 1368 19323 = 1368 * 14 +..

fullfish.tistory.com](https://fullfish.tistory.com/129)

더 나아가서 이를 이용해서

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++로

확장된 유클리드 알고리즘이란? ‘확장된’ 이라는 말이 붙었습니다. 그렇다면 유클리드 알고리즘이란 무엇일까요? 많은 분들이 알고 계신 것처럼, 유클리드 알고리즘은 최대공약수 (GCD) 를 구할

kbw1101.tistory.com](https://kbw1101.tistory.com/53)

참고