유클리드 호제법

1. 개요[편집]

---

유클리드 互除法 / Euclidean algorithm

두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로, 한국의 수학 교육과정에서는 다루지 않으나(자세하게 다루지는 않지만, 2015 개정 교육과정 중학교 1학년 수학 교과서에 짤막하게 나온다).[1] 정수론을 배우게 된다면 가장 먼저 나올 확률이 높은 공식이다. 일본의 수학 교육과정에서는 수학A로 다룬다. 하지만 여타 다른 교육과정 외 내용들이 그렇듯이 알아놓으면 몇몇 문제를 푸는데 굉장히 유용하다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 뜻의 '호제' 라는 단어가 따로 있지는 않다. 이 알고리즘은 유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라 한다. 알고리즘의 골자는 다음과 같다.

유클리드 호제법

두 양의 정수 [math(a,b\ (a>b))]에 대하여 [math(a=bq+r\,\left(0\le r<b\right))][2]

혹은 [math(a\equiv r\left(\text{mod}\,b\right))].

이라 하면, [math(a,b)]의 최대공약수는 [math(b,r)]의 최대공약수와 같다. 즉,{{{#!wiki style="margin:10px 0;text-align:center"

[math(\gcd\left(a,\ b\right)=\gcd\left(b,\ r\right))]}}}[math(r=0)]이라면, [math(a,b)]의 최대공약수는 [math(b)]가 된다.

2. 증명[편집]

---

[math(\gcd\left(a,\ b\right)=G)], [math(\gcd\left(b,\ r\right)=G')]이라 하자. 적당한 서로소인 정수 [math(A,B)]에 대해 [math(a=GA,b=GB)]가 성립한다. 이를 [math(a=bq+r)]에 대입하면, [math(GA=GBq+r)]이고, [math(r=G\left(A-Bq\right))]이다. 여기서 [math(G)]는 [math(b)]와 [math(r)]의 공약수임을 알 수 있다. 즉, [math(G)]는 [math(G')]의 약수이다.

[math(G'=mG)]로 두자. 그러면 적당한 서로소인 두 정수 [math(k,l)]에 대해 [math(GB=G'k=Gmk, G(A-Bq)=G'l=Gml)]이 성립한다.
양변을 [math(G)]로 나누면 [math(B=mk, A-Bq=ml)]이다.
[math(A=ml+Bq=ml+mkq=m\left(l+kq\right))]에서 [math(m)]은 [math(A)]와 [math(B)]의 공약수인데, [math(gcd(A,B)=1)]이므로 항상 [math(m=1)]이고 [math(G'=G)]이다.

3. 활용[편집]

---

알고리즘이라는 이름에 걸맞게, 위 성질을 한 번만 사용해서는 제대로 된 활용이 힘들다. 보통은 나머지가 [math(0)]이 될 때 까지 연속해서 사용한다. 예를 들면 아래와 같다.

3.1. 최대공약수[편집]

---

개요에도 쓰여있듯이, 이 알고리즘은 두 수의 최대공약수를 구할 때 쓸 수 있다. 한 예로 [math(12345)]와 [math(1234)]의 최대공약수를 구하고 싶다 하자. 위 알고리즘에 두 수를 대입하면,
따라서 두 수의 최대공약수는 [math(1)]임을 알 수 있다 (relatively prime).

3.2. 연분수[편집]

---

어떤 분수를 연분수 형태로 나타낼 때에도 이 알고리즘을 사용할 수 있다. 예를 들어 [math(\dfrac{23}9)]를 연분수 형태로 바꾼다 하자. 분자, 분모에 대해 알고리즘을 적용하면,
여기서 몫만 따오면, [math(\dfrac{23}9=2+\cfrac1{1+\cfrac1{1+\cfrac14}})]이다.

3.3. 소스 코드[편집]

---

손으로 계산할 때는 제수와 피제수의 값 크기를 비교해서 적절하게 배열하지만 수식이나 코드로 나타낼 때는 신경쓰지 않아도 되는데,

a<b

일 때

a mod b ≡ a(a%b==a)

이므로

Gcd(a,b)

는

Gcd(b,a)

를 호출한다. 즉 재귀 과정에서 자연스럽게 큰 값이

a

로, 작은 값이

b

로 들어간다.

3.3.1. C[편집]

---

int Euclidean(int a, int b)
{
    int r = a % b;
    if (r == 0) {
      return b;
    }
    return Euclidean(b, r);
}

3.3.1.1. 숏코딩[편집]

---

f(a,b){return b?f(b,a%b):a;}

3.3.2. Python[편집]

---

3.3.2.1. 반복문[편집]

---

def Euclidean(a, b):
    while b != 0:
        [a, b] = [b, a%b]
    return a

3.3.2.2. 재귀문[편집]

---

def Euclidean(a, b):
    r = b % a
    if r == 0:
        return a
    return Euclidean(r, a)

3.3.3. Java[편집]

---

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

3.4. 알고리즘으로서의 성능[편집]

---

두 수 [math(a>b)]를 나눈 나머지가 [math(r)]이라면 황금비 [math(\tau=(1+\sqrt{5})/2)]에 대해 [math(b<a/\tau)]이거나 [math(r<a/\tau^2)] 둘 중 하나가 성립한다. (만약 [math(b>a/\tau)]이면 [math(r=a-b<a/\tau^2)]이기 때문) 이를 이용하면 수학적 귀납법으로 "[math((a,b))]에 대해 호제법을 수행하면 나눗셈 횟수는 [math(\log_{\tau}(a)+1)] 이하이다"를 보일 수 있다. 피보나치 수열의 이웃한 두 항의 경우 정확히 저 횟수만큼 나눗셈을 하게 되므로 실질적인 최소값이라 할 수 있다. 더 나아가면 주어진 [math(a)]에 대해 나눗셈 횟수가 최대가 되는 [math(b)]는 [math(\lfloor a/\tau\rfloor)] 혹은 [math(\lfloor a/\tau\rfloor+1)]로 주어진다는 것을 보일 수 있지만 아주 중요한 것은 아니다.

어쨌든 나눗셈 횟수는 [math(\mathcal{O}(\log a))]이 된다. 정수 나눗셈 1회의 복잡도가 제수와 몫의 자리수 개수에 비례한다는, 즉 [math(\mathcal{O}(\log a\log (a/b)))]로 나타난다는 것까지 고려하면 (자세한 과정은 생략하겠지만) 유클리드 호제법 전체의 시간 복잡도가 [math(\mathcal{O}((\log a)^2))]로 나타남도 보일 수 있다. 정수의 입력 자체에서 [math(\mathcal{O}(\log a))]를 쓰는 것을 감안하면 꽤 좋은 효율이다.

하지만 유클리드 호제법도 최적의 알고리즘은 아니고(!!), 정말 큰 수의 경우에는 [math(\mathcal{O}(\log a(\log\log a)^2(\log\log\log a)))]이 보장되는 다른 준선형적 알고리즘들을 사용한다. 다행히도 2만 자리 넘어가는 정말 큰 수가 아닌 이상에야 호제법 정도면 크게 퍼포먼스가 떨어지진 않는다.

공간 복잡도 면에서는 위에 코드를 보면 알겠지만 변수 3개로도 충분하다. 다만 재귀를 쓰면 나눗셈 횟수만큼 호출 스택에서 [math(\mathcal{O}(\log n))]을 잡아먹으므로 쓰지 말자. [math(ax+by=d)]를 찾는 확장된 유클리드 알고리즘에서도 나눗셈 과정을 트랙할 필요는 없고, 코드를 잘 짜면 변수 4개로 처리할 수 있다.

4. 다항식에서의 호제법[편집]

---

두 정수뿐만 아니라 두 다항식의 최대공약수를 구할 때에도 쓰일 수 있다. 기본적인 틀은 동일하며, 단지 정수가 다항식으로 바뀐것 뿐. 자세한 내용은 아래와 같다.

두 다항식 [math(f\left(x\right),\ g\left(x\right))]에 관하여, [math(f\left(x\right)=g\left(x\right)Q\left(x\right)+R\left(x\right))]이고 [math(0\le\deg\left(R\left(x\right)\right)<\deg\left(g\left(x\right)\right))]이라 하면, [math(\gcd\left(f,\ g\right)=\gcd\left(g,\ R\right))]이 성립한다.

증명 방법 역시 정수의 경우와 동일하므로 생략한다. 단, 이 호제법이 성립하는 것은, 어디까지나 유클리드 정역의 환 위에서만이다.

4.1. 예시[편집]

---

문제

두 다항식 [math(x^3-3x^2+3x-1)], [math(x^2-1)]의 최대공약수를 구하시오.

풀이

{{{#!wiki style="text-align: center"

[math(x^3-3x^2+3x-1=\left(x^2-1\right)\left(x-3\right)+\left(4x-4\right))]}}}

{{{#!wiki style="text-align: center"

[math(x^2-1=\left(4x-4\right)\left(\dfrac{x+1}4\right))]}}}

따라서, [math(\gcd\left(x^3-3x^2+3x-1,\ x^2-1\right)=\gcd\left(x^2-1,\ 4x-4\right)=\gcd\left(4x-4,\ 0\right)=x-1)]이 처음 두 다항식의 최대공약수가 된다.

위 식에서는 원래 나머지를 비교하는 것이기에 [math(x=1)] 또는 [math(x=-1)]를 넣어서 풀면 쉽게 풀린다.

5. 유한체에서[편집]

---

시계 산술을 쓰는 유한체에서는 나눗셈의 정의를 다르게 정의해야 하는데, 이때 사용되는 것이 '확장된 유클리드 호제법'으로, 다음과 같이 정의된다.

[math(\alpha x+\beta y=\gcd(\alpha,\,\beta))]

이 방법을 이용해서 해당 정수의 '역수'[3]를 구한 뒤, 피제수에 곱하는 것을 유한체의 '나눗셈'으로 정의한다.

6. 관련 문서[편집]

---

• 최대공약수
• 나눗셈 정리
• 나머지 정리
• 베주 항등식