유클리드 호제법 (-互除法, Euclidean algorithm) 또는 유클리드 알고리즘 은 2개의 자연수 또는 정식(整式)의 최대공약수 를 구하는 알고리즘 의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지 를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년 경에 쓰인 《원론 》 제7권, 명제 1부터 3까지에 해당한다. 최소공배수, 최대공약수를 구하기 위해서는 다음과 같은 표를 쓴다.
1071과 1029의 최대공약수를 구하면,
1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
42는 21로 나누어 떨어진다. 따라서, 최대공약수는 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
∈
Z
{\displaystyle a,b\in \mathbb {Z} }
a
{\displaystyle a}
b
{\displaystyle b}
r
{\displaystyle r}
a
≥
b
{\displaystyle a\geq b}
r
{\displaystyle r}
0
≤
r
<
b
{\displaystyle 0\leq r<b}
a
{\displaystyle a}
b
{\displaystyle b}
(
a
,
b
)
{\displaystyle \left(a,b\right)}
(
a
,
b
)
=
(
b
,
r
)
.
{\displaystyle \left(a,b\right)=\left(b,r\right).}
상기한 1071과 1029에 대한 예시를 위와 같은 표현으로 적어보면,
(
1071
,
1029
)
=
(
1029
,
42
)
=
(
42
,
21
)
=
(
21
,
0
)
=
21
{\displaystyle \left(1071,1029\right)=\left(1029,42\right)=\left(42,21\right)=\left(21,0\right)=21}
처럼 쓸 수 있다.
a
,
b
∈
Z
{\displaystyle a,b\in \mathbb {Z} }
a
≥
b
{\displaystyle a\geq b}
그러면,
a
=
b
q
+
r
{\displaystyle a=bq+r}
q
,
r
{\displaystyle q,r}
0
≤
r
<
b
{\displaystyle 0\leq r<b}
(
a
,
b
)
=
d
,
a
=
d
α
,
b
=
d
β
{\displaystyle \left(a,b\right)=d,a=d\alpha ,b=d\beta }
α
{\displaystyle \alpha }
β
{\displaystyle \beta }
서로소 이다.
a
=
b
q
+
r
.
{\displaystyle a=bq+r.}
⇒
d
α
=
d
β
q
+
r
.
{\displaystyle \Rightarrow d\alpha =d\beta q+r.}
⇒
d
|
r
.
{\displaystyle \Rightarrow d|r.}
이제,
r
=
d
ρ
.
{\displaystyle r=d\rho .}
여기서 β와 ρ가 서로소라면, b(= dβ)와 r(=dρ)의 최대 공약수도 d가 된다.
만약
(
β
,
ρ
)
=
d
′
>
1
{\displaystyle \left(\beta ,\rho \right)=d'>1}
β
=
d
′
β
′
,
ρ
=
d
′
ρ
′
{\displaystyle \beta =d'\beta ',\rho =d'\rho '}
a
=
b
q
+
r
.
{\displaystyle a=bq+r.}
⇒
d
α
=
d
β
q
+
d
ρ
=
d
d
′
β
′
q
+
d
d
′
ρ
′
=
d
d
′
(
β
′
q
+
ρ
′
)
.
{\displaystyle \Rightarrow d\alpha =d\beta q+d\rho =dd'\beta 'q+dd'\rho '=dd'\left(\beta 'q+\rho '\right).}
⇒
α
=
d
′
(
β
′
q
+
ρ
′
)
.
{\displaystyle \Rightarrow \alpha =d'\left(\beta 'q+\rho '\right).}
이 되므로,
d
′
|
α
{\displaystyle d'|\alpha }
즉,
d
′
|
α
,
d
′
|
β
{\displaystyle d'|\alpha ,d'|\beta }
α
{\displaystyle \alpha }
β
{\displaystyle \beta }
모순 이다.
이는
(
β
,
ρ
)
=
d
′
>
1
{\displaystyle \left(\beta ,\rho \right)=d'>1}
(
β
,
ρ
)
=
1
{\displaystyle \left(\beta ,\rho \right)=1}
따라서 곧
(
b
,
r
)
=
d
{\displaystyle \left(b,r\right)=d}
A
{\displaystyle A}
B
{\displaystyle B}
Q
{\displaystyle Q}
R
{\displaystyle R}
A
=
B
Q
+
R
{\displaystyle A=BQ+R}
A
{\displaystyle A}
B
{\displaystyle B}
G
{\displaystyle G}
R
=
A
−
B
Q
{\displaystyle R=A-BQ}
R
{\displaystyle R}
G
{\displaystyle G}
G
{\displaystyle G}
R
{\displaystyle R}
B
{\displaystyle B}
R
=
G
R
1
{\displaystyle R=GR_{1}}
B
=
G
B
1
{\displaystyle B=GB_{1}}
R
1
{\displaystyle R_{1}}
B
1
{\displaystyle B_{1}}
R
1
{\displaystyle R_{1}}
B
1
{\displaystyle B_{1}}
C
{\displaystyle C}
R
1
=
C
R
2
{\displaystyle R_{1}=CR_{2}}
B
1
=
C
B
2
{\displaystyle B_{1}=CB_{2}}
R
=
G
R
1
=
G
C
R
2
{\displaystyle R=GR_{1}=GCR_{2}}
B
=
G
B
1
=
G
C
B
2
{\displaystyle B=GB_{1}=GCB_{2}}
A
=
B
Q
+
R
=
G
C
B
2
Q
+
G
C
R
=
G
C
(
B
2
Q
+
R
2
)
{\displaystyle A=BQ+R=GCB_{2}Q+GCR=GC(B_{2}Q+R_{2})}
A
{\displaystyle A}
B
{\displaystyle B}
C
G
{\displaystyle CG}
G
{\displaystyle G}
A
{\displaystyle A}
B
{\displaystyle B}
G
{\displaystyle G}
R
{\displaystyle R}
B
{\displaystyle B}
임의의 두 다항식 에 대해서도 유클리드 호제법과 같은 원리를 사용하여, 두 다항식의 최대차수공약다항식을 구할 수 있다. 즉, 다음과 같은 정리가 성립한다.
f
,
g
∈
C
[
x
]
{\displaystyle f,g\in \mathbb {C} [x]}
f
{\displaystyle f}
g
{\displaystyle g}
r
(
x
)
{\displaystyle r(x)}
deg
f
≥
deg
g
{\displaystyle \operatorname {deg} f\geq \operatorname {deg} g}
r
{\displaystyle r}
0
≤
deg
r
<
deg
g
{\displaystyle 0\leq \operatorname {deg} r<\operatorname {deg} g}
deg
f
{\displaystyle \operatorname {deg} f}
f
{\displaystyle f}
차수 를 뜻한다.)
f
{\displaystyle f}
g
{\displaystyle g}
(
f
,
g
)
{\displaystyle \left(f,g\right)}
(
f
,
g
)
=
(
g
,
r
)
.
{\displaystyle \left(f,g\right)=\left(g,r\right).}
f
(
x
)
=
x
3
+
2
x
2
+
x
,
g
(
x
)
=
x
2
−
1
{\displaystyle f(x)=x^{3}+2x^{2}+x,g(x)=x^{2}-1}
x
3
+
2
x
2
+
x
=
(
x
2
−
1
)
(
x
+
2
)
+
(
2
x
+
2
)
.
{\displaystyle x^{3}+2x^{2}+x=(x^{2}-1)(x+2)+(2x+2).}
x
2
−
1
=
(
2
x
+
2
)
(
x
−
1
2
)
.
{\displaystyle x^{2}-1=(2x+2)\left({\frac {x-1}{2}}\right).}
위 식으로부터,
(
x
3
+
2
x
2
+
x
,
x
2
−
1
)
=
(
x
2
−
1
,
2
x
+
2
)
=
(
2
x
+
2
,
0
)
=
x
+
1
{\displaystyle \left(x^{3}+2x^{2}+x,x^{2}-1\right)=\left(x^{2}-1,2x+2\right)=\left(2x+2,0\right)=x+1}
(
C
[
x
]
{\displaystyle \mathbb {C} [x]}
가역원 이므로, 공약다항식에 대해서 말할 때에는 곱해주어서 계수를 조절해줄 수 있다.)
f
∈
C
[
x
]
,
g
∈
C
[
x
]
∖
{
0
}
{\displaystyle f\in \mathbb {C} [x],g\in \mathbb {C} [x]\setminus \{0\}}
deg
f
≥
deg
g
{\displaystyle \operatorname {deg} f\geq \operatorname {deg} g}
그러면,
C
[
x
]
{\displaystyle \mathbb {C} [x]}
유클리드 정역 이므로,
f
=
g
q
+
r
{\displaystyle f=gq+r}
q
,
r
{\displaystyle q,r}
r
=
0
{\displaystyle r=0}
deg
r
<
deg
g
{\displaystyle \operatorname {deg} r<\operatorname {deg} g}
(
f
,
g
)
=
d
,
f
=
d
f
′
,
g
=
d
g
′
{\displaystyle \left(f,g\right)=d,f=df',g=dg'}
deg
(
f
′
,
g
′
)
=
0
{\displaystyle \operatorname {deg} (f',g')=0}
f
=
g
q
+
r
.
{\displaystyle f=gq+r.}
⇒
d
f
′
=
d
g
′
q
+
r
.
{\displaystyle \Rightarrow df'=dg'q+r.}
⇒
d
|
r
.
{\displaystyle \Rightarrow d|r.}
이제,
r
=
d
r
′
.
{\displaystyle r=dr'.}
만약
(
g
′
,
r
′
)
=
d
′
{\displaystyle \left(g',r'\right)=d'}
상수 가 아니라면,
g
′
=
d
′
g
″
,
r
′
=
d
′
r
″
{\displaystyle g'=d'g'',r'=d'r''}
f
=
g
q
+
r
.
{\displaystyle f=gq+r.}
⇒
d
f
′
=
d
g
′
q
+
d
r
′
=
d
d
′
g
″
q
+
d
d
′
r
″
=
d
d
′
(
g
″
q
+
r
″
)
.
{\displaystyle \Rightarrow df'=dg'q+dr'=dd'g''q+dd'r''=dd'\left(g''q+r''\right).}
⇒
f
′
=
d
′
(
g
″
q
+
r
″
)
.
{\displaystyle \Rightarrow f'=d'\left(g''q+r''\right).}
이 되므로,
d
′
|
f
′
{\displaystyle d'|f'}
즉,
d
′
|
f
′
,
d
′
|
g
′
{\displaystyle d'|f',d'|g'}
deg
(
f
′
,
g
′
)
=
0
{\displaystyle \operatorname {deg} (f',g')=0}
그러므로
deg
(
g
′
,
r
′
)
=
0
{\displaystyle \operatorname {deg} \left(g',r'\right)=0}
(
g
,
r
)
=
d
{\displaystyle \left(g,r\right)=d}
입력으로 두 수 m,n(m>n)이 들어온다.
n이 0이라면, m을 출력하고 알고리즘을 종료한다.
m이 n으로 나누어 떨어지면, n을 출력하고 알고리즘을 종료한다.
그렇지 않으면, m을 n으로 나눈 나머지를 새롭게 m에 대입하고, m과 n을 바꾸고 3번으로 돌아온다. 위 과정은 “n, m에 대해서 나머지 연산을 실시할 수 있다”라는 조건에만 의존하므로, 정수환 뿐 아니라, 임의의 유클리드 정역 에 대해도 똑같은 과정을 거치면 공약인자가 구해진다.
int gcd ( int a , int b )
{
return b ? gcd ( b , a % b ) : a ;
}
int gcd ( int a , int b )
{
int c ;
while ( b )
{
c = a % b ;
a = b ;
b = c ;
}
return a ;
}
def gcd ( m , n ):
if m < n :
m , n = n , m
if n == 0 :
return m
if m % n == 0 :
return n
else :
return gcd ( n , m % n )
def gcd ( m , n ):
while n != 0 :
t = m % n
( m , n ) = ( n , t )
return abs ( m )
def gcd ( m , n ):
while n ! = 0 :
if m < n :
m , n = n , m
if n == 0 :
return m
if m % n == 0 :
return n
def gcd ( m , n ):
if n == 0 :
return m
mod = m % n
if mod != 0 :
m , n = n , mod
return gcd ( m , n )
else :
return n
public static int gcd ( int p , int q )
{
if ( q == 0 ) return p ;
return gcd ( q , p % q );
}
let rec gcd m n =
match n with
| 0 -> m
| _ -> gcd n ( m % n )
gcd ( A , 0 , D ) :- A >= 0 , D is A , !.
gcd ( A , 0 , D ) :- A < 0 , D is - 1 * A , !.
gcd ( A , B , D ) :- A < 0 , B > 0 , !, gcd ( - 1 * A , B , D ).
gcd ( A , B , D ) :- A >= 0 , B < 0 , !, gcd ( A , - 1 * B , D ).
gcd ( A , B , D ) :- A < 0 , B < 0 , !, gcd ( - 1 * A , - 1 * B , D ).
gcd ( A , B , D ) :- A >= 0 , B > 0 , A >= B , R is A mod B , !, gcd ( B , R , D ).
gcd ( A , B , D ) :- A >= 0 , B > 0 , B > A , !, gcd ( B , A , D ).
정수 m, n 의 최대공약수 (Greatest Common Divisor)를 gcd(m,n)와 같이 나타낼 때, 확장된 유클리드 호제법을 이용하여, am + bn = gcd(m,n)의 해가 되는 정수 a, b 짝을 찾아낼 수 있다.(a, b 중 한개는 보통 음수가 된다.) 이 식은 베주의 정의 라고 한다. 위에서 든 예의 경우,
1071 = 1 * 1029 + 42
1029 = 24 * 42 + 21
42 = 2 * 21
특히, m, n이 서로소 (gcd(m,n) = 1)인 경우 유용한데, 그럼 위의 식은 am + bn = 1이 되고, 여기서 a는 모듈로 연산의 곱의 역원(modular multiplicative inverse)이 되기 때문이다.
f
,
g
∈
C
[
x
]
{\displaystyle f,g\in \mathbb {C} [x]}
(
f
,
g
)
{\displaystyle \left(f,g\right)}
f
p
+
g
q
=
(
f
,
g
)
{\displaystyle fp+gq=\left(f,g\right)}
p
,
q
∈
C
[
x
]
{\displaystyle p,q\in \mathbb {C} [x]}
f
(
x
)
=
x
3
+
2
x
2
+
x
,
g
(
x
)
=
x
2
−
1
{\displaystyle f(x)=x^{3}+2x^{2}+x,g(x)=x^{2}-1}
x
3
+
2
x
2
+
x
=
(
x
2
−
1
)
(
x
+
2
)
+
(
2
x
+
2
)
.
{\displaystyle x^{3}+2x^{2}+x=(x^{2}-1)(x+2)+(2x+2).}
x
2
−
1
=
(
2
x
+
2
)
(
x
−
1
2
)
.
{\displaystyle x^{2}-1=(2x+2)\left({\frac {x-1}{2}}\right).}
이므로
2
x
+
2
=
x
3
+
2
x
2
+
x
−
(
x
2
−
1
)
(
x
+
2
)
{\displaystyle 2x+2=x^{3}+2x^{2}+x-(x^{2}-1)(x+2)}
가 된다.
특히,
(
f
,
g
)
=
1
{\displaystyle \left(f,g\right)=1}
f
p
+
g
q
=
1
{\displaystyle fp+gq=1}
p
,
q
∈
C
[
x
]
{\displaystyle p,q\in \mathbb {C} [x]}
유클리드 호제법을 이용하여 나머지를 취하는 조작을, 최악의 경우라도 작은 수를 십진법으로 표시한 자리수의 5배를 반복하기 전에 최대공약수에 이른다(라메의 정리 ).
최대공약수를 구할 때, 소인수 분해를 하는 것이 더 쉽다고 생각하는 사람이 있을지도 모르지만, 위 정리는 소인수 분해를 이용하는 것보다도 유클리드 호제법을 실시하여 구하는 것이 훨씬 빠르다는 것을 말한다.
실제로 계산량 이론에서 최대공약수를 요구하는 것은 “쉬운 문제”로서 알려져 있고, 소인수 분해는 “어려운 문제”로 여겨지고 있다. 입력된 2개의 정수의 비트수를 n이라고 하면, 유클리드 알고리즘은 Θ(n) 회의 나눗셈으로 최대공약수를 구할 수 있다.
위에 든 예에서 나온 1071과 1029의 최대공약수를 구하는 과정은 다음과 같이 나타낼 수 있다.
1071
=
1029
×
1
+
42
1029
=
42
×
24
+
21
42
=
21
×
2
{\displaystyle {\begin{matrix}1071&=&1029\times 1+42\\1029&=&42\times 24+21\\42&=&21\times 2\end{matrix}}}
즉,
1071
/
1029
=
1
+
42
/
1029
1029
/
42
=
24
+
21
/
42
42
/
21
=
2
{\displaystyle {\begin{matrix}1071/1029&=&1+42/1029\\1029/42&=&24+21/42\\42/21&=&2\end{matrix}}}
따라서,
1071
1029
=
1
+
1
24
+
1
2
{\displaystyle {\frac {1071}{1029}}=1+{\frac {1}{24+{\frac {1}{2}}}}}
이와 같이, n와 m(n>m)의 최대공약수를 구할 때의 유클리드 호제법의 나눗셈의 모양은 유리수 n/m 의 연분수 전개와 같다.
![{\displaystyle f,g\in \mathbb {C} [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8c6fb3be3b54aec0e6c0b500c962dc31b27a647d)
![{\displaystyle \mathbb {C} [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/244ad3bb0a1d2ff11dde84c4edee1171f670fdb0)
![{\displaystyle f\in \mathbb {C} [x],g\in \mathbb {C} [x]\setminus \{0\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bfebb4ae82e61e9f26da5a66027e970ed351ce88)
![{\displaystyle p,q\in \mathbb {C} [x]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/80ecb66de6bf74492400822c3ea3dadd7d0210c1)
