유클리드 호제법

에 마지막으로 수정됐습니다.

1. 개요2. 증명3. 활용
3.1. 최대공약수3.2. 연분수3.3. 소스 코드
3.3.1. C3.3.2. Python
4. 다항식에서의 호제법
4.1. 예시
5. 관련 문서


Euclidean Algorithm

1. 개요[편집]

두 양의 정수, 혹은 두 다항식의 최대공약수를 구하는 방법으로, 한국의 수학 교육과정에서는 다루지 않는다.[1] 하지만 여타 다른 교육과정 외 내용들이 그렇듯이 알아놓으면 몇몇 문제를 푸는데 굉장히 유용하다. 알려주지는 않으면서 문제는 낸다. 호제법(互除法)이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다. 이 알고리즘유클리드의 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라 한다. 알고리즘의 골자는 다음과 같다.
두 양의 정수 a,b(b>a)a,b\,\left(b>a\right)에 대하여 b=aq+r,(0r<a)b=aq+r,\,\left(0\leq r<a\right)라 하면, a,ba,b최대공약수a,ra,r최대공약수와 같다. 즉, gcd(a,b)=gcd(a,r)\gcd\left(a,b\right)=\gcd\left(a,r\right).

2. 증명[편집]

gcd(a,b)=G\gcd\left(a,b\right)=G라 하자. 그럼 적당한 서로소정수 A,BA,B에 대해 a=GA,b=GBa=GA,\,b=GB가 성립한다. 이를 b=aq+rb=aq+r에 대입하면, GB=GAq+rGB=GAq+r이고, r=G(BAq)r=G\left(B-Aq\right)이다. 여기서 GGaarr의 공약수임을 알 수 있다. 만약 AABAqB-Aq가 서로소이면 증명이 끝난다.
gcd(A,BAq)=m\gcd\left(A,B-Aq\right)=m이라고 하면, 적당한 서로소인 정수 k,lk,l에 대해 A=mk,BAq=mlA=mk,\,B-Aq=ml이 성립한다. 한편, B=ml+Aq=ml+mkq=m(l+kq)B=ml+Aq=ml+mkq=m\left(l+kq\right)이다. 즉, gcd(A,B)=m\gcd\left(A,B\right)=m이다. 그런데 A,BA,B는 서로소이므로, m=1m=1이다. 이는 곧 AABAqB-Aq가 서로소임을 의미한다.

3. 활용[편집]

알고리즘이라는 이름에 걸맞게, 위 성질을 한 번만 사용해서는 제대로 된 활용이 힘들다. 보통은 나머지가 0이 될 때 까지 연속해서 사용한다. 이를 간단한 표로 나타내면 아래와 같다.
{{|b=aq1+r1,0<r1<ab=aq_1+r_1,\,0<r_1<a
a=r1q2+r2,0<r2<r1a=r_1q_2+r_2,\,0<r_2<r_1
r1=r2q3+r3,0<r3<r2r_1=r_2q_3+r_3,\,0<r_3<r_2
\vdots
rn2=rn1qn+rn,0<rn<rn1r_{n-2}=r_{n-1}q_n+r_n,\,0<r_n<r_{n-1}
rn1=rnqn+1r_{n-1}=r_nq_{n+1}
gcd(a,b)=rn\gcd\left(a,b\right)=r_n|}}

3.1. 최대공약수[편집]

개요에도 쓰여있듯이, 이 알고리즘은 두 수의 최대공약수를 구할 때 쓸 수 있다. 한 예로 12345와 1234의 최대공약수를 구하고 싶다 하자. 위 알고리즘에 두 수를 대입하면,
12345=123410+512345=1234\cdot10+5
1234=5246+41234=5\cdot246+4
5=41+15=4\cdot1+1
4=144=1\cdot4
곧 두 수의 최대공약수는 1임을 알 수 있다.

3.2. 연분수[편집]

어떤 분수를 연분수 형태로 나타낼 때에도 이 알고리즘을 사용할 수 있다. 예를 들어 239\frac{23}{9}를 연분수 형태로 바꾼다 하자. 분자, 분모에 대해 알고리즘을 적용하면,
23=92+523=9\cdot2+5
9=51+49=5\cdot1+4
5=41+15=4\cdot1+1
4=144=1\cdot4
여기서 몫만 따오면, 239=2+11+11+14\frac{23}{9}=2+\frac{1}{1+\frac{1}{1+\frac{1}{4}} }이다.

3.3. 소스 코드[편집]

3.3.1. C[편집]

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

3.3.2. Python[편집]

def Euclidean(a, b):

  r = b % a

  if r == 0:
    return a

  else:
    Euclidean(r, a)

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

두 정수뿐만 아니라 두 다항식최대공약수를 구할 때에도 쓰일 수 있다. 기본적인 틀은 동일하며, 단지 정수가 다항식으로 바뀐것 뿐. 자세한 내용은 아래와 같다.
두 다항식 f(x),g(x)f\left(x\right),g\left(x\right)에 관하여, f(x)=g(x)q(x)+r(x),0degr(x)<degg(x)f\left(x\right)=g\left(x\right)q\left(x\right)+r\left(x\right),\,0\leq\deg{r\left(x\right)}<\deg{g\left(x\right)}이라 하면, gcd(f,g)=gcd(g,r)\gcd\left(f,g\right)=\gcd\left(g,r\right)이 성립한다.
증명 방법 역시 정수의 경우와 동일하므로 생략한다.

4.1. 예시[편집]

x33x2+3x1,x21x^3-3x^2+3x-1,\,x^2-1의 최대공약수를 구해보자. 그럼,
x33x2+3x1=(x21)(x3)+(4x4)x^3-3x^2+3x-1=\left(x^2-1\right)\left(x-3\right)+\left(4x-4\right)
x21=(4x4)(x+14)x^2-1=\left(4x-4\right)\left(\frac{x+1}{4}\right)
따라서, gcd(x33x2+3x1,x21)=gcd(x21,4x4)=gcd(4x4,0)=x1\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이 처음 두 다항식의 최대공약수가 된다.
위 식에서는 원래 나머지를 비교하는 것 이기에 x에 1 또는 -1를 넣어서 풀면 쉽게 풀린다.

5. 관련 문서[편집]

[1] 그렇다고 아주 접하지 않는 건 아닌데, 사교육을 받지 않은 구세대라면 방학교재에서 봤을 것이다.