유클리드 호제법

1. 개요

유클리드 호제법은 두 정수의 최대공약수를 효율적으로 계산하는 알고리즘이다. 기원전 300년경 유클리드의 저서에 처음 등장하며, 정수, 다항식, 실수 등 다양한 수학적 대상에 적용될 수 있다. 이 알고리즘은 최대공약수를 구하는 데 사용될 뿐 아니라, 베주의 항등식, 디오판토스 방정식, 유한체, 연분수, 정수 인수분해 등 다양한 분야에 응용된다. 유클리드 호제법은 계산 복잡도가 낮아 매우 효율적이며, 확장된 유클리드 호제법은 베주의 항등식의 해를 찾는 데 사용된다.

2. 역사

유클리드 호제법은 기원전 300년경 유클리드의 저서 《원론》에 처음 등장한다. 하지만, 이 알고리즘은 유클리드 이전에 이미 알려져 있었을 가능성이 크다. 인도와 중국에서도 유클리드 호제법과 유사한 알고리즘이 독립적으로 발견되었으며, 이는 주로 천문학 및 달력 계산에 활용되었다.

19세기에 들어서면서, 유클리드 호제법은 가우스 정수와 같은 새로운 수 체계의 개발에 영향을 주었으며, 대수학의 발전에도 기여하였다. 현대에는 정수 관계 알고리즘, RSA 암호화 알고리즘 등 다양한 분야에 응용되고 있다.

3. 작동 원리

유클리드 호제법은 주어진 두 수의 최대공약수를 구하는 알고리즘이다. 두 수 a와 b (a > b)의 최대공약수를 구하기 위해 다음과 같은 단계를 거친다.

* b가 0이면, a를 출력하고 알고리즘을 종료한다.
* a가 b로 나누어 떨어지면, b를 출력하고 알고리즘을 종료한다.
* 그렇지 않으면, a를 b로 나눈 나머지를 새로운 a에 대입하고, a와 b를 바꾸고 위의 과정을 반복한다.

이 과정은 나머지가 0이 될 때까지 반복되며, 마지막으로 나눈 수가 최대공약수가 된다.

예를 들어 1071과 1029의 최대공약수를 구하는 과정은 다음과 같다.

* 1071을 1029로 나눈 나머지는 42이다.
* 1029를 42로 나눈 나머지는 21이다.
* 42를 21로 나눈 나머지는 0이다.

따라서 최대공약수는 21이다.

이러한 과정은 "n, m에 대해서 나머지 연산을 실시할 수 있다"라는 조건에만 의존하므로, 정수환뿐 아니라 임의의 유클리드 정역에 대해서도 똑같은 과정을 거치면 공약인자를 구할 수 있다.

유클리드 호제법은 최대공약수를 구하는 대상인 두 정수를 폭과 높이로 설정한 직사각형 내에서 붉은색 사선의 직선을 그리는 과정으로도 표현할 수 있다. 붉은색 사선은 직사각형의 한쪽 구석에서 시작하여 45도 각도로 그려지며, 변에 닿으면 직각으로 반사된다. 직선이 반대편 변에 닿으면, 직전 반사 지점에서 수직으로 선을 그어 직사각형을 두 부분으로 나눈다. 이 과정을 반복하여 더 작은 직사각형을 만들고, 직선이 직사각형의 모서리에 닿으면 알고리즘이 종료된다. 이때 마지막 직사각형의 짧은 변의 길이가 최대공약수가 된다.

3.1. 정수의 경우

두 정수 a와 b의 최대공약수는 유클리드 호제법을 통해 다음과 같이 계산될 수 있다.

* 1071과 1029의 최대공약수를 구하는 과정은 다음과 같다.
1071을 1029로 나눈 나머지는 42이다.
1029를 42로 나눈 나머지는 21이다.
** 42를 21로 나눈 나머지는 0이다.
따라서, 최대공약수는 21이다.

* 78696과 19332의 최대공약수를 구하는 과정은 다음과 같다.
78696 ＝ 19332×4 ＋ 1368
19332 ＝ 1368×14 ＋ 180
1368 ＝ 180×7 ＋ 108
180 ＝ 108×1 ＋ 72
108 ＝ 72×1 ＋ 36
72 ＝ 36×2 ＋ 0
따라서, 최대공약수는 36이다.

유클리드 호제법의 정당성은 다음 정리를 통해 증명될 수 있다.
:$a,\; b\; \backslash in\; \backslash mathbb\{Z\}$이고, $a$를 $b$로 나눈 나머지가 $r$이라고 하자. (여기서 $a\backslash ge\; b$이고, $r$은 인 정수.)

:$\backslash left(a,\; b\backslash right)\; =\; \backslash left(b,\; r\backslash right).$

* 1071과 1029에 대한 예시를 위와 같은 표현으로 적어보면,
:$\backslash left(1071,\; 1029\backslash right)\; =\; \backslash left(1029,\; 42\backslash right)\; =\; \backslash left(42,\; 21\backslash right)\; =\; \backslash left(21,\; 0\backslash right)=21$
과 같이 쓸 수 있다.

$a,\; b\; \backslash in\; \backslash mathbb\{Z\}$이고, $a\backslash ge\; b$라고 하자.

그러면, $a=bq+r$을 만족하는 유일한 정수 $q,\; r$이 존재한다. 이때, 이다.

$\backslash left(a,\; b\backslash right)\; =\; d$, $a=d\backslash alpha$, $b=d\backslash beta$라고 하자. 즉, $\backslash alpha$와 $\backslash beta$는 서로소이다.
:$a=bq+r.$
:$\backslash Rightarrow\; d\backslash alpha\; =d\backslash beta\; q+r.$
:$\backslash Rightarrow\; d|r.$(즉, r은 d의 배수)

이제, $r=d\backslash rho.$라고 하자.

여기서 β와 ρ가 서로소라면, b(= dβ)와 r(=dρ)의 최대 공약수도 d가 된다.

만약 $\backslash left(\backslash beta,\; \backslash rho\backslash right)\; =\; d\text{'}\; >\; 1$(서로소가 아닌 수, 즉 다른 공약수를 가지는 수)이라면, $\backslash beta\; =\; d\text{'}\backslash beta\text{'}$, $\backslash rho=d\text{'}\backslash rho\text{'}$으로 두었을 때,
:$a=bq+r.$
:$\backslash Rightarrow\; d\backslash alpha\; =\; d\backslash beta\; q+d\backslash rho\; =\; d\; d\text{'}\backslash beta\text{'}\; q\; +\; d\; d\text{'}\; \backslash rho\text{'}=\; d\; d\text{'}\backslash left(\backslash beta\text{'}\; q\; +\; \backslash rho\text{'}\backslash right).$
:$\backslash Rightarrow\; \backslash alpha\; =\; d\text{'}\backslash left(\backslash beta\text{'}\; q\; +\; \backslash rho\text{'}\backslash right).$

이 되므로, $d\text{'}|\backslash alpha$이다. (즉, α는 d'의 배수 )

즉, $d\text{'}|\backslash alpha,\; d\text{'}|\backslash beta$가 되어 $\backslash alpha$와 $\backslash beta$는 서로소라는 것에 모순이다.

이는 $\backslash left(\backslash beta,\; \backslash rho\backslash right)\; =\; d\text{'}\; >\; 1$ 라는 가정에서 나타나는 모순이므로 $\backslash left(\backslash beta,\; \backslash rho\backslash right)\; =\; 1$(즉, β와 ρ는 서로소)이다.

따라서 $\backslash left(b,\; r\backslash right)\; =\; d$이다.

쉽게 풀면 다음과 같다.

$A$를 $B$로 나눈 몫을 $Q$, 나머지를 $R$이라고 할 때, $A=BQ+R$로 나타낼 수 있다. $A$와 $B$의 최대 공약수를 $G$라고 할 때, $R=A-BQ$이므로 $R$도 $G$로 나눌 수 있게 된다. 즉, $G$는 $R$과 $B$의 공약수가 된다. 따라서 $R=GR\_1$, $B=GB\_1$라고 쓸 수 있다. 이때 $R\_1$, $B\_1$은 서로소, 즉 공약수를 갖지 않는다. $R\_1$, $B\_1$가 공약수 $C$를 가지면 $R\_1=CR\_2$, $B\_1=CB\_2$가 되어, $R=GR\_1=GCR\_2$, $B=GB\_1=GCB\_2$라고 쓸 수 있다. 그러면, $A=BQ+R=GCB\_2Q+GCR=GC(B\_2Q+R\_2\; )$가 된다. 이때 $A$, $B$의 최대 공약수가 $CG$가 되어 $G$가 최대공약수라는 것과 모순된다. 따라서 $A$와 $B$의 최대 공약수 $G$는 $R$과 $B$의 최대 공약수이다.

3.2. 다항식의 경우

다항식에도 유클리드 호제법을 적용하여 최대차수공약다항식을 구할 수 있다. 두 다항식 $f,\; g\; \backslash in\; \backslash mathbb\{C\}[x]$ ($\backslash operatorname\{deg\}f\backslash ge\; \backslash operatorname\{deg\}g$)에 대해, $f$를 $g$로 나눈 나머지를 $r(x)$라 하면 () 다음이 성립한다.

:$\backslash left(f,\; g\backslash right)\; =\; \backslash left(g,\; r\backslash right).$

여기서 $\backslash left(f,\; g\backslash right)$는 $f$와 $g$의 최대차수공약다항식을 의미한다.

예를 들어 $f(x)=x^3+2x^2+x,\; g(x)=x^2-1$인 경우,

:$x^3+2x^2+x=(x^2-1)(x+2)+(2x+2).$
:$x^2-1=(2x+2)\backslash left(\backslash frac\{x-1\}\{2\}\backslash right).$

이므로, $\backslash left(x^3+2x^2+x,\; x^2-1\backslash right)\; =\; \backslash left(x^2-1,\; 2x+2\backslash right)=\backslash left(2x+2,\; 0\backslash right)=x+1$이다.

이는 $\backslash mathbb\{C\}[x]$에서 상수가 가역원이므로, 공약다항식의 계수를 조절할 수 있기 때문이다.

다항식에 대한 유클리드 호제법의 정당성은 정수의 경우와 유사하게 증명할 수 있다. $f\backslash in\backslash mathbb\{C\}[x],g\; \backslash in\; \backslash mathbb\{C\}[x]\backslash setminus\backslash \{0\backslash \}$이고, $\backslash operatorname\{deg\}f\backslash ge\; \backslash operatorname\{deg\}g$라고 하자.

유클리드 정역의 성질에 의해, $f=gq+r$을 만족하는 유일한 다항식 $q,\; r$이 존재한다. (단, $r=0$이거나 )

$\backslash left(f,\; g\backslash right)\; =\; d,\; f=df\text{'},\; g=dg\text{'}$라고 하면 ($\backslash operatorname\{deg\}(f\text{'},g\text{'})=0$),

:$f=gq+r$
:$\backslash Rightarrow\; df\text{'}\; =dg\text{'}q+r$
:$\backslash Rightarrow\; d|r$.

$r=dr\text{'}$라고 하고, $\backslash left(g\text{'},\; r\text{'}\backslash right)\; =\; d\text{'}$이 상수가 아니라고 가정하면, $g\text{'}\; =\; d\text{'}g$, r'=d'r으로 두었을 때,

:$f=gq+r$
:$\backslash Rightarrow\; df\text{'}\; =\; dg\text{'}q+dr\text{'}\; =\; d\; d\text{'}g$ q + d d' r= d d'\left(g q + r\right)
:$\backslash Rightarrow\; f\text{'}\; =\; d\text{'}\backslash left(g$ q + r\right)
이 되므로, $d\text{'}|f\text{'}$이다.

즉, $d\text{'}|f\text{'},\; d\text{'}|g\text{'}$이 되어 $\backslash operatorname\{deg\}(f\text{'},g\text{'})=0$이라는 것에 모순이다.

따라서 $\backslash operatorname\{deg\}\backslash left(g\text{'},\; r\text{'}\backslash right)\; =\; 0$이고, 이는 $\backslash left(g,\; r\backslash right)\; =\; d$임을 의미한다.

4. 확장된 유클리드 호제법

확장된 유클리드 호제법은 두 정수 m, n의 최대공약수(gcd(m,n))뿐만 아니라, mx + ny = gcd(m, n)을 만족하는 정수 x, y를 찾는 방법이다. 이 식은 베주의 정의라고 불린다.

특히, m, n이 서로소인 경우(gcd(m,n) = 1), 이 알고리즘은 mx + ny = 1을 만족하는 정수해 (x, y)를 제공하며, 여기서 x는 m의 모듈로 연산에서의 곱셈 역원이 된다. 즉, x는 m으로 나눈 나머지가 같은 수들의 집합에서 곱셈에 대한 역원 역할을 한다.

일반적으로, m = r₀, n = r₁에서 유클리드 호제법의 각 과정은 다음과 같이 반복될 수 있다.

:
:
:
:$...$
:$r\_\{h\; -\; 1\}\; =\; k\_\{h\; -\; 1\}r\_\{h\}\; +\; 0$

행렬을 사용하면, 다음과 같이 표현할 수 있다.

:$$
\begin{pmatrix}
r_{0} \\
r_{1} \\
\end{pmatrix}
=
\begin{pmatrix}
k_{0} & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
k_{1} & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
k_{2} & 1 \\
1 & 0 \\
\end{pmatrix}
...
\begin{pmatrix}
k_{h-1} & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
r_{h} \\
0 \\
\end{pmatrix}

$$
K_{i}=
\begin{pmatrix}
k_{i} & 1 \\
1 & 0 \\
\end{pmatrix}라고 하면, $|K\_\{i\}|=-1$이므로 역행렬 $K\_\{i\}^\{-1\}$이 존재하고,

:$$
\begin{pmatrix}
k_{h-1} & 1 \\
1 & 0 \\
\end{pmatrix}^{-1}
...
\begin{pmatrix}
k_{2} & 1 \\
1 & 0 \\
\end{pmatrix}^{-1}
\begin{pmatrix}
k_{1} & 1 \\
1 & 0 \\
\end{pmatrix}^{-1}
\begin{pmatrix}
k_{0} & 1 \\
1 & 0 \\
\end{pmatrix}^{-1}
\begin{pmatrix}
r_{0} \\
r_{1} \\
\end{pmatrix}
=
\begin{pmatrix}
r_{h} \\
0 \\
\end{pmatrix}


$K\_\{i\}^\{-1\}=\backslash begin\{pmatrix\}$
0 & 1 \\
1 & -k_{i} \\
\end{pmatrix}을 고려하면,

:$$
\begin{pmatrix}
0 & 1 \\
1 & -k_{h - 1} \\
\end{pmatrix}
...
\begin{pmatrix}
0 & 1 \\
1 & -k_{2} \\
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & -k_{1} \\
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & -k_{0} \\
\end{pmatrix}
\begin{pmatrix}
m \\
n \\
\end{pmatrix}
=
\begin{pmatrix}
\gcd(m, n) \\
0 \\
\end{pmatrix}
이 된다.

:$$
\begin{pmatrix}
x & y \\
u & v \\
\end{pmatrix}
=
\begin{pmatrix}
0 & 1 \\
1 & -k_{h - 1} \\
\end{pmatrix}
...
\begin{pmatrix}
0 & 1 \\
1 & -k_{2} \\
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & -k_{1} \\
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & -k_{0} \\
\end{pmatrix}
이라고 놓고, 유클리드 호제법의 각 과정에서 얻어진 $k\_\{0\}$, $k\_\{1\}$, $k\_\{2\}$등을 사용하여 우변을 계산하면, 좌변의 $x$, $y$ 가 구해지며, 이는 베주 항등식 mx + ny = gcd(m,n)을 만족한다.

4.1. 정수의 경우

확장된 유클리드 호제법을 이용하면, 주어진 두 정수 m, n에 대해 am + bn = gcd(m, n)을 만족하는 정수 a, b를 구할 수 있다. 이 식은 베주의 정의라고 불린다. 특히, m, n이 서로소(gcd(m,n) = 1)인 경우, 이 식은 am + bn = 1이 되고, 여기서 a는 모듈로 연산의 곱의 역원이 된다.

예를 들어, 1071과 462의 최대공약수(GCD)를 구하는 과정은 다음과 같다.

* 1071 = 2 * 462 + 147
* 462 = 3 * 147 + 21
* 147 = 7 * 21 + 0

따라서 gcd(1071, 462) = 21이다. 이를 통해,

* 21 = 1029 - 24 * 42
* = 1029 - 24 * (1071 - 1 * 1029)
* = -24 * 1071 + 25 * 1029

이므로, a = -24, b = 25가 된다.

일반적으로, m = r₀, n = r₁에서 유클리드 호제법의 각 과정을 반복하면 다음과 같다.

* r₀ = k₀r₁ + r₂ ( 0 < r₂ < r₁)
* r₁ = k₁r₂ + r₃ ( 0 < r₃ < r₂)
* r₂ = k₂r₃ + r₄ ( 0 < r₄ < r₃)
* ...
* r_{h - 1} = k_{h - 1}r_h + 0

이 과정에서 행렬을 이용하여 표현하면 다음과 같다.

:$$
\begin{pmatrix}
r_{0} \\
r_{1} \\
\end{pmatrix}
=
\begin{pmatrix}
k_{0} & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
k_{1} & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
k_{2} & 1 \\
1 & 0 \\
\end{pmatrix}
...
\begin{pmatrix}
k_{h-1} & 1 \\
1 & 0 \\
\end{pmatrix}
\begin{pmatrix}
r_{h} \\
0 \\
\end{pmatrix}

여기서 K_i = 라고 하면, |K_i| = -1 이므로 K_i^-1이 존재하고,

:$$
\begin{pmatrix}
k_{h-1} & 1 \\
1 & 0 \\
\end{pmatrix}^{-1}
...
\begin{pmatrix}
k_{2} & 1 \\
1 & 0 \\
\end{pmatrix}^{-1}
\begin{pmatrix}
k_{1} & 1 \\
1 & 0 \\
\end{pmatrix}^{-1}
\begin{pmatrix}
k_{0} & 1 \\
1 & 0 \\
\end{pmatrix}^{-1}
\begin{pmatrix}
r_{0} \\
r_{1} \\
\end{pmatrix}
=
\begin{pmatrix}
r_{h} \\
0 \\
\end{pmatrix}


K_i^-1 = 을 고려하면,

:$$
\begin{pmatrix}
0 & 1 \\
1 & -k_{h - 1} \\
\end{pmatrix}
...
\begin{pmatrix}
0 & 1 \\
1 & -k_{2} \\
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & -k_{1} \\
\end{pmatrix}
\begin{pmatrix}
0 & 1 \\
1 & -k_{0} \\
\end{pmatrix}
\begin{pmatrix}
m \\
n \\
\end{pmatrix}
=
\begin{pmatrix}
\gcd(m, n) \\
0 \\
\end{pmatrix}

이 된다.

이라고 놓고, 유클리드 호제법의 각 과정에서 얻어진 k₀, k₁, k₂ 등을 사용하여 우변을 계산하면, 좌변의 x, y가 구해지며, 이는 베주 항등식 mx + ny = gcd(m,n)을 만족한다.

4.2. 다항식의 경우

$f,\; g\; \backslash in\; \backslash mathbb\{C\}[x]$의 최대차수공약다항식을 $\backslash left(f,\; g\backslash right)$라고 하면, $fp\; +\; gq\; =\; \backslash left(f,\; g\backslash right)$인 $p,\; q\; \backslash in\; \backslash mathbb\{C\}[x]$를 찾을 수 있다. 예를 들어,

$f(x)=x^3+2x^2+x,\; g(x)=x^2-1$일 때,

:$x^3+2x^2+x=(x^2-1)(x+2)+(2x+2).$
:$x^2-1=(2x+2)\backslash left(\backslash frac\{x-1\}\{2\}\backslash right).$
이므로

:$2x+2=x^3+2x^2+x-(x^2-1)(x+2)$
이다.

특히, $\backslash left(f,\; g\backslash right)=1$인 경우 $fp\; +\; gq\; =\; 1$인 $p,\; q\; \backslash in\; \backslash mathbb\{C\}[x]$를 찾을 수 있다.

5. 응용

유클리드 호제법의 다른 버전에서는 각 단계에서 음의 나머지의 크기가 일반적인 양의 나머지보다 작을 때 몫을 1 증가시킨다. 이전에는 다음 방정식이 있었다.

: r_k−2 = q_k r_k−1 + r_k

이는 r_k−1 > r_k > 0을 가정했다. 그러나 다음과 같은 대안적인 음의 나머지 e_k를 계산할 수 있다.

: r_k−2 = (q_k + 1) r_k−1 + e_k (만약 r_k−1 > 0 인 경우)
: r_k−2 = (q_k − 1) r_k−1 + e_k (만약 r_k−1 < 0 인 경우)

만약 r_k가 e_k^영어 < r_k일 때 e_k^영어로 대체된다면, 다음을 만족하는 유클리드 호제법의 변형을 얻게 된다.

: r_k^영어 ≤ r_k−1^영어 / 2

레오폴트 크로네커는 이 버전이 유클리드 호제법의 어떤 버전보다도 가장 적은 단계를 필요로 함을 보였다. 더 일반적으로, 모든 입력 숫자 a와 b에 대해, 단계 수가 최소가 되는 것은 을 만족하도록 q_k^영어가 선택될 때이며, 여기서 $\backslash varphi$는 황금비이다.

6. 계산 복잡도

유클리드 호제법은 매우 효율적인 알고리즘으로, 입력되는 두 수의 자릿수에 비례하는 시간 안에 최대공약수를 찾을 수 있다. 라메의 정리에 따르면, 유클리드 호제법을 이용하여 나머지를 취하는 조작을 최악의 경우라도 작은 수를 십진법으로 표시한 자리수의 5배를 반복하기 전에 최대공약수에 이른다. 일반적으로 유클리드 호제법은 소인수분해보다 훨씬 빠른 알고리즘으로 알려져 있다.

실제로, 계산 복잡성 이론에서는 최대공약수를 구하는 것은 "쉬운 문제"로 알려져 있으며, 소인수 분해는 "어려운 문제"라고 여겨진다. 입력된 두 정수 가운데 작은 정수 n의 자릿수를 d라고 하면, 유클리드 호제법에서는 O(d) 회의 나눗셈으로 최대공약수를 구할 수 있다. 자릿수 d는 O(log n)이므로, 유클리드 호제법에서는 O(log n) 회의 나눗셈으로 최대공약수를 구할 수 있다.

7. 다른 수 체계로의 확장

유클리드 호제법은 정수뿐만 아니라 다른 수 체계에도 적용할 수 있도록 일반화되었다. 예를 들어, 유리수 `n/m`의 연분수 전개는 유클리드 호제법의 나눗셈 모양과 같다.

1071과 462의 최대공약수를 구하는 예시를 통해 이를 확인할 수 있다. 유클리드 호제법을 적용하면 다음과 같은 과정을 거친다.

8. 같이 보기

* 최대공약수
* 베주 항등식
* 확장된 유클리드 호제법
* 연분수