유클리드 호제법(Euclidean algorithm)

사진출처: 위키피디아

 

유클리드 호제법은 두 정수의 최대공약수(Greatest common divisor: GCD)를 구하는 효율적이고 간단한 알고리즘입니다. 기원전 300년경 그리스 수학자 유클리드(Euclid)가 편찬한 유클리드 원론(기하학 원론)에서 처음 소개돼었습니다. 가장 오래된 알고리즘으로 알려져 있습니다.

두 정수 \(a\)와 \(b\)가 주어졌고 \(a\)는 \(b\)보다 크다고 하겠습니다. \(\left(a, b\in \mathbb{Z}이고\;\;a \gt b\right)\). \(a\)를 \(b\)로 나누면 \(a \div b = q\)이고 이는 \(a = bq + r\) 이렇게 다시 쓸 수 있습니다. 여기서 \(q\)는 몫(quotient)이고 \(r\)은 나머지(remainder)입니다. 여기서 \(a\)와 \(b\)의 최대공약수를 \(gcd(a, b)\)라고 표현하면 아래식이 성립합니다.

$$
gcd(a, b) = gcd(b, r)
$$

\(a\)와 \(b\)의 최대공약수는 \(b\)와 \(r\)의 최대공약수와 같습니다. 여기서 다시 \(b\)를 \(r\)로 나눈 나머지 \(r'\)을 구하고 다시 \(r\)을 \(r'\)로 나누는 과정 반복하다가 나머지가 0이 되었을 때 나누는 수가 최대공약수가 됩니다. 몇가지 예를 들어보겠습니다.

$$
\begin{matrix}
gcd(4098, 2024) = 2\\
4098 \div 2024 = 2 \cdots 나머지는\;50
\end{matrix}
$$
$$
\begin{matrix}
gcd(50, 2024) = 2\\
2024 \div 50 = 40 \cdots 나머지는\;24
\end{matrix}
$$
$$
\begin{matrix}
gcd(50, 24) = 2\\
50 \div 24 = 2 \cdots 나머지는\;2
\end{matrix}
$$
$$
\begin{matrix}
gcd(2, 24) = 2\\
24 \div 2 = 12 \cdots 나머지는\;0
\end{matrix}
$$
$$
\begin{matrix}
gcd(2, 0) = 2
\end{matrix}
$$

두 수 4098, 2024의 최대공약수는 2입니다.

 

$$
\begin{align*}
& gcd(123456, 9999) \\
& = gcd(3468, 9999) \\
& = gcd(3468, 3063) \\
& = gcd(405, 3063) \\
& = gcd(405, 228) \\
& = gcd(177, 228) \\
& = gcd(177, 51) \\
& = gcd(24, 51) \\
& = gcd(24, 3) \\
& = gcd(0, 3)
\end{align*}
$$
두 수 123456, 9999의 최대공약수는 2입니다.

 

 

정리하자면 다음과 같습니다.  

1. 두 정수 중 큰 수를 작은 수로 나눈 나머지로 바꿉니다. (만약 \(a \gt b\)라면 \(a = a\;mod\;b\))
2. 두 정수 중 한쪽이 0이 될 때까지 반복합니다. 이때 0이 아닌 쪽이 최대공약수입니다.

이에 대한 증명은 이 글에서 다루지 않습니다.

 

 

다음은 위 내용을 C언어로 구현한 코드입니다. 유클리드 호제법의 시간 복잡도는 \(O\left(log\left(a+b\right)\right)\)입니다.

int gcd(int a, int b)
{
	while (a >= 1 && b >= 1)
	{
		if (a >= b)
			a = a % b;
		else
			b = b % a;
	}

	if (a > 1)
		return a;
	return b;
}

int recur_gcd(int a, int b)
{
	if (b == 0)
		return a;
	else
		return recur_gcd(b, a % b);
}