유클리드 호제법 / 확장 유클리드 호제법

유클리드 호제법 / 확장 유클리드 호제법

< Euclidean algorithm >

---

  유클리드 호제법 

  유클리드 호제법 이란 두 자연수 사이의 최대공약수(GCD) 를 구하는 알고리즘 이다. gcd(a, b) == a 와 b 의 최대공약수 라고 할 때 알고리즘에 사용되는 식은 다음과 같다.

 

gcd(a, b) == gcd(b, a % b) ... (b <= a)

 

  a, b (b < a) 의 최대공약수는 b, a 를 b 로 나눈 값의 나머지의 최대공약수와 같다.

 

  Code

dataType gcd(dataType a, dataType b) {
	if (b == 0) return a;

	if (a < b) return gcd(a, b % a);
	else return gcd(b, a % b);
}

  dataType 은 자연수 값에 해당되는 자료형을 사용해야 한다. (C++ 기준 int, unsigned int, long long, unsigned long long 등..)

---

  확장 유클리드 호제법   

  확장 유클리드 호제법은 베주 항등식 (Bezout's Identity) 의 명제를 기반으로 해를 구하는 알고리즘 이다. 베주 항등식은 다음과 같다.

 

  베주 항등식 (Bezout's Identity)

  ax + by = d 를 만족하는 (x, y) 정수해는 d 의 값이 gcd(a, b) 의 배수일 때 존재하며, 이 존재하는 경우 나오는 값들만 (x, y) 의 정수해가 될 수 있다. 즉, d % gcd(a, b) == 0 인 경우이다.

  만약 4x + 3y = 2 이라는 방적식이 있다고 하자. 이 때 (x, y)의 정수해는 ... ,(-1, 2), (2, -2), (5, -6), ... 등이 된다. 4, 3 의 최대공약수는 1이며 우변의 2는 1의 배수이기 때문에 정수해가 존재하는 것 이다. 또한 이렇게 해가 무수히 많은 방정식은 부정 방정식 이라고 부르며 정수해를 가지는 부정 방정식을 디오판토스 방정식 이라고 부른다.

  그렇다면 14x + 6y = 3 이라는 방정식은 정수해가 존재할까? 14, 6 의 최대공약수는 2 이다. 하지만 우변의 3 은 2 의 배수가 아니다. 따라서 이는 베주 항등식에 해당되지 않으며 정수해가 존재하지 않는다.

  

  확장 유클리드 호제법은 베주 항등식에 대해서 유클리드 호제법 과정을 역으로 따라감으로써 정수해를 만족하는 x, y 의 값들을 구할 수 있는 알고리즘이다. 17x + 5y = 11 을 예로 들어보았다. (a = 17, b = 5 가 된다.)

 

  이 경우는 우선 gcd(17, 5) == 1, 11%1 = 0 을 만족하므로 베주 항등식이다. 따라서 확장 유클리드 호제법을 사용하여 x, y 의 정수해를 구할 수 있다. 베주 항등식에선 우선 좌변만 가지고 확장 유클리드 호제법을 사용한다.

 

  

  s, t 는 x, y 의 현재 값을 의미한다. 1, 2 번째 줄은 항상 위와 같이 초기화를 한다. s 가 1, t 가 0 인 경우 r은 a 값인 17이 되고 s 가 0, t 가 1 인 경우 r은 b 의 값인 5가 된다.

 

  3번째 줄에 q는 1, 2 번째 줄의 r 값을 나눈 값의 몫, 3번째 줄의 3은 이의 나머지에 해당된다. 그리고 3번째 줄의 s, t 의 값은 이전 {1번째 줄의 (s, t)} - {3번째 줄의 q} * {2번째 줄의 (s, t)} 이다. n번째 줄의 값들을 계산할 때 n-1, n-2 번째 줄이 참고가 되는 것 이다. 이는 r의 값이 0이 될 때 까지 같은 작업이 계속해서 이어지며 이를 귀납법을 통한 식으로 나타내면 다음과 같다.

 

 

  r의 값이 0이 되면, 0이 된 부분을 n번째 줄 이라고 할 때 n-1번째의 s, t 값을 참고하여 x, y의 값을 정의할 수 있다. 위 케이스에선 빨간색 글자로 된 부분인 -2, 7이 x, y의 값 정의에 쓰인다.

 

방정식에서 우변은, gcd(a, b) 의 배수로 정의되어 있었다. 이 경우엔 위처럼 곱해지니 배수만큼 s, t 를 곱해주면 된다. 따라서 (x, y) 의 식은 ..., (-22, 77), (-17, 60), (-12, 43) ... 가 된다.

 

  Code

dType extendedEuclidMul(dType a, dType b) {
	if (gcd(a, b) != 1) return -1;

	dType s0 = 1, t0 = 0, r0 = a;
	dType s1 = 0, t1 = 1, r1 = b;
	dType q = r0 / r1;
	dType temp = 0;


	while (r1) {
		q = r0 / r1;

		temp = s0 - q * s1;
		s0 = s1;
		s1 = temp;

		temp = t0 - q * t1;
		t0 = t1;
		t1 = temp;

		temp = r0 % r1;
		r0 = r1;
		r1 = temp;
	}

	// a * x + b * y = gcd(a, b) * c 의 베주 항등식에서
	// x = s0 * c + b * k
	// y = t0 * c - a * k

	// 문제에 맞게 k 값을 정한 후 값을 return 하면 된다.

	/*
		..
		return ..
	*/
}