이곳은 개발을 위한 베타 사이트 입니다.
기여내역은 언제든 초기화될 수 있으며, 예기치 못한 오류가 발생할 수 있습니다.

유클리드 호제법

덤프버전 :

[[대수학|대수학

Algebra
]]

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



정수론
Number Theory


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



1. 개요
2. 증명
3. 활용
3.2. 연분수
3.3. 소스 코드
3.3.2. Python
3.3.2.1. 반복문
3.3.2.2. 재귀문
3.3.3. Java
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)]임을 알 수 있다 (relatively prime).


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[편집]


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. 관련 문서[편집]





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