최근 수정 시각 : 2022-08-11 22:03:47

유클리드 호제법

[[대수학|대수학
Algebra
]]
{{{#!wiki style="margin:0 -10px -5px; word-break: keep-all;"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="letter-spacing: -1px"
{{{#!wiki style="margin:-6px -1px -11px"
이론
기본 대상 연산 · 항등식( 가비의 이 · 곱셈 공식( 통분 · 약분) · 인수분해) · 부등식( 절대부등식) · 방정식( 풀이 · ( 무연근 · 허근 · 비에트의 정리( 근과 계수의 관계) · 제곱근( 이중근호 · 개방법) · 환원 불능) · 부정 · 불능) · 비례식 · 다항식 · 산술( 시계 산술)
수 체계 자연수( 소수) · 정수( 음수) · 유리수 · 실수( 무리수( 초월수) · 초실수) · 복소수( 허수) · 사원수 · 대수적 수 · 벡터 공간
다루는 대상과 주요토픽
대수적 구조
군(group) 대칭군 · 기본군 · 자유군 · 리 군 · 괴물군 · 점군 · 순환군 · 군의 작용 · 동형 정리 · 실로우 정리
환(ring) 아이디얼
체(field) 갈루아 이론
대수 가환대수 · 리 대수 · 불 대수( 크로네커 델타)
마그마 · 반군 · 모노이드 자유 모노이드 · 가환 모노이드
선형대수학 벡터 · 행렬 · 텐서( 텐서곱) · 벡터 공간( 선형사상) · 가군(Module) · 내적 공간( 그람-슈미트 과정 · 수반 연산자)
정리 · 추측
대수학의 기본정리 · 나머지 정리 · 유클리드 호제법 · 부분분수분해 · PID 위의 유한생성 가군의 기본정리 · 산술·기하 평균 부등식 · 바이어슈트라스 분해 정리 · 호지 추측미해결 · 가환대수에서의 호몰로지 추측미해결
관련 하위 분야
범주론 함자 · 수반 · 자연 변환 · 모나드 · 쌍대성 · 층 이론( 층들) · 토포스 이론 · 타입 이론
대수기하학 대수다양체 · 스킴 · 사슬 복합체( 에탈 코호몰로지) · 모티브
대수적 정수론 타원곡선 · 디오판토스 방정식 · 유리근 정리 · 모듈러성 정리
가환대수학 스펙트럼 정리
표현론
대수적 위상수학 호모토피
기타 및 관련 문서
수학 관련 정보 · 추상화 · 1학년의 꿈 · 노름 · 혼합계산 · 분배법칙 · 교환법칙 · 결합법칙 · 교재 }}}}}}}}}}}}

정수론
Number Theory
{{{#!wiki style="margin:0 -10px -5px"
{{{#!folding [ 펼치기 · 접기 ]
{{{#!wiki style="margin:-6px -1px -11px"
공리
페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질
산술
나눗셈 약수 · 배수 배수 · 약수( 소인수) · 소인수분해( 목록) · 공배수 · 공약수 · 최소공배수 · 최대공약수
약수들의 합에 따른 수의 분류 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수
정리 베주 항등식 · 산술의 기본정리 · 나눗셈 정리
기타 유클리드 호제법 · 서로소
디오판토스 방정식 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버츠와 스위너톤-다이어 추측(미해결)
모듈러 연산
잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리
소수론
수의 분류 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수( 사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수
분야 대수적 정수론 · 해석적 정수론
산술함수 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수· 체비쇼프 함수 · 소수생성다항식
정리 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)( 천의 정리) · 폴리냑 추측(미해결) · 소수 정리
기타 에라토스테네스의 체 · 윌런스의 공식
}}}}}}}}} ||

1. 개요2. 증명3. 활용
3.1. 최대공약수3.2. 연분수3.3. 소스 코드
3.3.1. C3.3.2. Python
3.3.2.1. 반복문3.3.2.2. 재귀문
3.4. 알고리즘으로서의 성능
4. 다항식에서의 호제법
4.1. 예시
5. 유한체에서6. 관련 문서

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,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)]이 될 때 까지 연속해서 사용한다. 예를 들면 아래와 같다.
[math(\begin{aligned}a&=bq_1+r_1\,\left(0<r_1<b\right)\\b&=r_1q_2+r_2\,\left(0<r_2<r_1\right)\\r_1&=r_2q_3+r_3\,\left(0<r_3<r_2\right)\\&\ \ \vdots\\r_{n-2}&=r_{n-1}q_n+r_n\,\left(0<r_n<r_{n-1}\right)\\r_{n-1}&=r_nq_{n+1}\end{aligned}\\\therefore\gcd\left(a,\ b\right)=r_n)]

3.1. 최대공약수

개요에도 쓰여있듯이, 이 알고리즘은 두 수의 최대공약수를 구할 때 쓸 수 있다. 한 예로 [math(12345)]와 [math(1234)]의 최대공약수를 구하고 싶다 하자. 위 알고리즘에 두 수를 대입하면,
[math(\begin{aligned}12345&=1234\cdot 10+5\\1234&=5\cdot 246+4\\5&=4\cdot 1+1\\4&=1\cdot 4\end{aligned}\\\therefore\gcd\left(12345,\ 1234\right)=1)]
따라서 두 수의 최대공약수는 [math(1)]임을 알 수 있다.

3.2. 연분수

어떤 분수를 연분수 형태로 나타낼 때에도 이 알고리즘을 사용할 수 있다. 예를 들어 [math(\dfrac{23}9)]를 연분수 형태로 바꾼다 하자. 분자, 분모에 대해 알고리즘을 적용하면,
[math(\begin{aligned}23&=9\cdot 2+5\\9&=5\cdot 1+4\\5&=4\cdot 1+1\\4&=1\cdot 4\end{aligned})]
여기서 몫만 따오면, [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

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

3.3.1.1. 숏코딩
#!syntax cpp
f(a,b){return b?f(b,a%b):a;}

3.3.2. Python

3.3.2.1. 반복문
#!syntax python
def Euclidean(a, b):
    while b != 0:
        r = a % b
        a = b
        b = r
    return a

3.3.2.2. 재귀문
#!syntax python
def Euclidean(a, b):
    r = b % a
    if r == 0:
        return a
    return Euclidean(r, a)

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/taurfloor)] 혹은 [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. 관련 문서



[1] 그렇다고 아주 접하지 않는 건 아닌데, 사교육을 받지 않은 구세대라면 방학교재에서 봤을 것이다. [2] 혹은 [math(a\equiv r\left(\text{mod}\,b\right))]. [3] 유리수체에서의 역수와는 다르다. 유리수체에서의 정수의 역수는 1보다 작을 수 밖에 없는데, 유한체의 역수는 유한체 내부의 원소여야 하기 때문에 1보다 클 수 밖에 없다. 예를 들어서 5를 법으로 하는 유한체의 경우, 1의 역원은 1이지만 2의 역원은 3, 3의 역원은 2, 4의 역원은 4 자기 자신이 된다.