베주의 항등식, 확장 유클리드 알고리즘

* 베주의 항등식, 확장 유클리드 알고리즘

  [해당 포스팅은 두 정수의 최대 공약수를 구하는 유클리드 알고리즘 지식을 요구합니다.]

  확장 유클리드 알고리즘을 설명하기 앞서 베주의 항등식을 통해 확장 유클리드 알고리즘의 (x, y) 해가 반드시 존재함을 보고 넘어가겠습니다.

* 베주의 항등식

  확장 유클리드 수식과 완전히 동일합니다만, 여기선 (x, y) 해가 반드시 존재함에 포커싱을 두고 있다는 점을 다시 인지하며 명제를 봐봅시다.

   0이 아닌 정수 a, b에 대해 d를 a와 b의 최대 공약수라고 하면 수식을 만족하는 해 (x, y)는 반드시 존재한다.

  특히 a와 b가 서로소이고 d=1이라면 베주의 항등식에 의해 정수해가 반드시 존재해야 합니다.

* 계산 방식

  먼저 유클리드 알고리즘을 이용하여 해를 어떻게 구해나가는지 알아보도록 합시다. 이 과정은 베주의 항등식 증명에도 사용되므로 제대로 이해하고 가는 것이 중요합니다.

ex) 

1. 먼저 유클리드 알고리즘을 수행합니다. 이는 a와 b에 대한 최대공약수 d를 구하기 위함입니다.

2. d(=gcd(a, b))부터 유클리드 알고리즘을 거꾸로 거슬러 올라갑니다. 이 때 계산은 뺄셈 연산이 들어가게 됩니다. 이 과정을 통해 베주의 등식꼴로 나타낼 수 있습니다.

이렇게 일 때 베주의 항등식을 만족하는 해 (x, y)=(3, -8)을 찾을 수 있습니다.

* 베주의 항등식 증명

0이 아닌 정수 a와 b에 대해 a를 b로 나눈 나머지 r1은 반드시 |b|보다 작습니다. 또 gcd(a, b)=gcd(b, r1)임은 유클리드 알고리즘에서 이미 증명한 사실을 알고 있습니다. 이 사실을 이용하여 아래처럼 유클리드 알고리즘을 나열할 수 있습니다. 과정에 a와 b를 넣은 것을 확인하고 넘어갑시다.

  위 유클리드 과정을 자세히 확인하면 이 0이 아닌 나머지 중에서 가장 마지막 수라는 사실을 알 수 있습니다. 이는 곧 유클리드 알고리즘이 다음에 끝난다는 걸 의미합니다. 따라서 가 gcd(a, b)=d입니다. 또 는 와  조합으로 구할 수 있습니다. 이를 끝까지 따라가다보면 a와 b의 식으로 나타낼 수 있음을 알 수 있습니다.

  따라서 정수해 (x, y)는 반드시 존재합니다.

* 확장 유클리드 알고리즘

  확장 유클리드 알고리즘은 주어진ㄴ 정수 a, b에 대해 다음 수식을 만족하는 (x, y)를 찾는 알고리즘입니다.

  해가 존재함은 베주의 정리에 의해 이미 증명되어 있습니다.

  마찬가지로 유클리드 알고리즘을 거꾸로 올라가며 정수 x, y를 찾을 수 있습니다.

* 순서

먼저 점화식에서 a의 계수 x와 b의 계수 y에 대해 점화식을 도출해줍니다.

, 

  우리는 위의 베주의 항등식을 통해 수열을 구해나가는 도중에 gcd(a, b)를 구할 수 있다는 것을 이미 알고 있습니다. 따라서 좌변 가 gcd(a, b)일 때의 우변 에서 계수를 구하면 그것이 곧 우리가 구하고자 하는 해 (x, y)임이 명확하죠.

  처음부터 점화식을 구했으니, 초항만 구해주면 됩니다.

  이 초항을 가지고 총 세개의 점화식을 반복적으로 연산하며 진행해주시면 됩니다. (점화식 구조를 보면 마치 피보나치 수열이루는 것을 볼 수 있습니다. 이 구조를 이용한 몇 가지 공리가 또 있긴합니다. 아직 계획은 없지만 흥미가 생기면 포스팅할게요 ㅎㅎ)

* 슈도 코드(재귀)

EXTENDED-EUCLID(a, b)
  if b == 0
    return (a, 1, 0)
  else (di, xi, yi) = EXTENDED-EUCLID(b, a mod b)
  (d,x, y) = (di, yi, xi - (a / b) y);
  return (d, x, y)

* 문제 풀이 팁

  위의 설명에서는 정수해를 구하라는 디오판토스 방정식에서 통용되는 내용입니다만, 보통의 문제에서는 제약을 거는 경우가 있습니다. 계수를 가지고 노는 경우가 많은데요, x과 y가 0이면 안된다던지, x 또는 y가 반드시 양수이어야 한다던지, x와 y의 차이가 k만큼 차이가 나야 한다던지 등의 여러가지 응용이 많습니다. 이런 종류의 문제들은 정리해서 따로 포스팅할 예정입니다. 아마 올해(2019) 안에 하지 않을까 싶네요.