Euclid Algorithm

자연수 세계 - 서론과 이야기거리 로 돌아가기

유클리드 알고리듬

어떤 두 자연수 a, b가 주어지고 a가 b 보다 크다면 a를 b로 나누면 몫과 b보다 작은 나머지를 가진다. 이 사실은 더 생각할 것도 없이 당연해 보인다. 예를 들어 29와 3에 대해서는

$29=3\cdot 9+2$

로 여기서 몫은 9, 나머지는 2가 된다. 당연해 보이는 이 생각을 일반식으로 나타내면 지금 우리가 생각하지 못하는 여러 정리를 살펴보는데 아주 유용하다. 무엇보다 이것은 최대공약수를 찾거나 1차 2변수 디오판테스 방정식을 푸는데 쓰이고 산술의 가장 기초적인 정리라 할 수 있는 산술의 기본정리를 증명하는데 쓰일 수 있다.

최대공약수를 찾는 알고리듬

최대공약수나 서로소 관계에 대하여 정의와 기본 성질에 대하여 최대공약수 편을 참고하기 바란다. 최대공약수의 정의만 여기에 옮기면 다음과 같다.

정의 : 최대공약수  : a, b의 공약수 중 가장 큰 것을 'a, b의 최대공약수'라 한다.

이미 우리가 보았듯이 주어진 두 정수에 대하여 최대공약수는 항상 존재한다. 따라서 남은 단계는 어떻게 하면 최대공약수를 찾을까 하는 문제로 귀결된다. 이는 0이 아닌 모든 주어진 정수 a, b에 대하여 최대공약수를 찾는 효율적인 알고리듬은 있을까? 라는 문제다.

알고리듬 1

a의 약수를 찾는다 : 2부터 제곱해서 a가 나오는 수보다 작은 모든 양의 정수로 나눠본다.

a, b 공약수를 찾는다 : 앞 단계에서 찾은 약수로 b를 나눠본다.

최대 공약수를 찾는다 : 앞 단계서 찾은 공약수 중 가장 큰 것을 찾는다.

알고리듬 2

a 를 소수들의 곱으로 나타낸다.

b 를 소수들의 곱으로 나타낸다.

같은 소수들만 뽑아 곱한다. 이 곱이 최대공약수.

유클리드 알고리듬

$a=b\cdot q_{1}+r_{1}$ 인 $q_{1},r_{1}$을 찾는다. ($0<r_{1}<b$ 이도록)

$b=r_{1}\cdot q_{2}+r_{2}$ 인 $q_{2},r_{2}$을 찾는다. ($0<r_{2}<r_{1}$ 이도록)

$r_{1}=r_{2}\cdot q_{3}+r_{3}$ 인 $q_{3},r_{3}$을 찾는다. ($0<r_{3}<r_{3}$ 이도록)

$r_{n-1}=r_{n}\cdot q_{n+1}+0$ 일 때까지 비슷한 과정 과정 반복

$(a,b)\ =\ r_{n}$

이 과정은 끝이 날 수밖에 없다. 왜냐하면

$b>r_{1}>r_{1}>r_{1}>\cdots >0$

에 다다를 수밖에 없기 때문이다. 기껏해야 b보다는 작은 단계로 최대공약수를 찾게 된다. (왜 그런가? 어떤 경우에 최대의 경우가 될까?)

이는 유클리드의 원론 (영어판 유클리드 원론)의 7권 1-3의 성질을 현대적 식으로 나타낸 것이다.

예를 들어

• 12, 4 의 경우 12 = 4 * 3 + 0 이므로 (4, 12) = 4
• 163, 43의 경우

$163=43\cdot 3+34$

$43=34\cdot 1+9$

$34=9\cdot 3+7$

$9=7\cdot 1+2$

$7=2\cdot 3+1$

$2=1\cdot 2+0$

(163, 43) = 1

• 1014, 273의 경우

$1014=273\cdot 3+195$

$273=195\cdot 1+78$

$195=78\cdot 2+39$

$78=39\cdot 2+0$

(1014. 273) = 39

위의 세 알고리듬 중 어떤 알고리듬이 가장 확실하고 빠를까? 앞의 단원들에서 말하였듯 어떤 수를 나누도록 하는 약수를 찾는 문제는 다루는 수가 클수록 대단히 계산의 양이 많은 복잡한 알고리듬이다. 게다가 찾은 수들에서 가장 큰 것을 찾는 알고리듬을 다시 해야한다. 그에 비해 마지막 유클리드의 알고리듬은 확실하고 빠르다.

유클리드 알고리듬 증명

유클리드 알고리듬이 최대공약수를 찾는 매우 효율적인 알고리듬이라는 것은 짐작할 수 있다. 그렇다면 이를 수학적 증명은 어떻게 될까? 증명은

$a=b\cdot q+r$ 이면 (a,b) = (b,r)이다.

라는 사실에 기초한다. 위의 사실은

1. a, b의 공약수는 반드시 b,r의 공약수 이고
2. b,r의 공약수는 반드시 a, b의 공약수다

라는 두 사실을 보이면 된다. 1)의 경우 : a, b의 공약수 k가 있다고 해보자. 그러면

$a=k\cdot a'\ ,\ b=k\cdot b'$

$k\cdot a'-k\cdot b'=r$

이므로 k는 r의 약수이기도 하다. 따라서 b, r의 공약수가 된다. 2)의 경우도 마찬가지 방법이다. 증명 끝.

앞에서 보였던 예를 다시 보면

(1024, 73) = (273, 195) = (195, 78) = (78,39) = 39

(163, 43) = (43, 34) = (9, 7) = (7,2) = ( 2,1) = 1

인 것이다.

유클리드 알고리듬의 응용

주어진 두 수의 최대공약수를 찾는 아주 효율적인 알고리듬이 유클리드 알고리듬이다. 따라서 최대공약수 개념이 쓰이는 여러 지점에서 유클리드 알고리듬은 '알고리듬적'인 설명을 하여 이해하는데 도움을 준다. 여기서는 응용되는 사례들을 본다.

유클리드 알고리듬을 이용하여 산술의 기본정리 증명의 기초정리를 증명하기

산술의 기본정리를 증명하는 동안 그 기초적인 역할을 하였던 정리를 더듬어보자. 다름 아닌

정리1 : 소수 p가 두수의 곱 ab를 나누면 p는 a를 나누거나 b를 나눈다.

이다. 그리고 이 정리를 증명하기 위하여

기초정리 : (a, b) = d 이면 다음 조건을 만족하는 정수 l, k를 찾을 수 있다

$d=ka+lb$

를 썼다.

이 기초정리를 유클리드 알고리듬을 써서 증명할 수도 있다.

유클리드 알고리듬 첫 단계에서 $r_{1},q_{1}$을 찾았다면

$r_{1}=a-q_{1}b$이고 여기서 a, b에 다른 정수들을 곱하여 $r_{1}$를 나타낸 것이다. 마찬가지로

$r_{2}=b-q_{2}r_{1}$이고 $r_{1}$ 은 a, b를 포함하고 '선형으로' 있으므로 a, b에 다른 정수들을 곱하여 $r_{1}$를 나타낸 것이다. 이 방법은 계속 이어져 마침내

$r_{n}$에 대해서도 마찬가지다. 증명 끝.

연속분수 나타내기

위의 예에서 두 자연수 163, 43 이라는 두 자연수는 공통약수를 갖지 않은 관계다.즉, (163, 43) = 1. 이 두 수의 관계를 분수로 표시해 나타내보면

$163=43\cdot 3+34$		${\frac {163}{43}}=3+{\frac {34}{43}}=3+{\frac {1}{\frac {43}{34}}}$
$43=34\cdot 1+9$		${\frac {43}{34}}=1+{\frac {9}{34}}=1+{\frac {1}{\frac {34}{9}}}$
$34=9\cdot 3+7$		${\frac {34}{9}}=3+{\frac {7}{9}}=3+{\frac {1}{\frac {9}{7}}}$
$9=7\cdot 1+2$		${\frac {9}{7}}=1+{\frac {2}{7}}=1+{\frac {1}{\frac {7}{2}}}$
$7=2\cdot 3+1$		${\frac {7}{2}}=3+{\frac {1}{2}}$

따라서 이를 연속분수로 나타내면

${\frac {163}{43}}=3+{\cfrac {1}{1+{\cfrac {1}{3+{\cfrac {1}{1+{\cfrac {1}{3+{\cfrac {1}{2}}}}}}}}}}$

위에서 보는 것 처럼 유클리드 알고리듬은 주어진 두수를 연속분수로 나타내는 데 유용하다.

직선형 디오판테스 방정식의 해 구하기

최대공약수의 부분에서 우리는 다음의 사실에 박수를 보냈다.

정리 : 'ay - bx = c 를 참이도록 하는 정수 해 (x,y)가 있다.' $\Leftrightarrow$ 'c는 (a,b)로 나뉜다.'

이는 직선형 디오판테스 방정식의 계수 a, b의 최대공약수를 찾는 문제가 그 방정식의 해를 구하는 문제와 겉으로 말만 다를 뿐 논리적으로 같은 힘을 갖고 있다는 것을 안 것이다. 따라서 유클리드 알고리듬을 써서 최대공약수를 '빠르게' 찾는다면 해를 구할 수 있다. 이 알고리듬을 위해서 최대공약수의 응용을 보라.

• 예 : 273 x + 1014 y = 156 의 해를 구하라.

유클리드 알고리듬으로 최대공약수를 구한다 : (273, 1014) = 39 , 156 = 39*4 다. O.K.!

최대공약수로 양쪽 항을 모두 나눈다 : 7x + 26 y = 4

7x + 26 y = 1의 해를 하나 찾는다.

26 = 3*7 + 5

7 = 1*5 + 2

5 = 2*2 + 1

2 = 2*1 + 0

에서

5 = 26 + (-3)*7

2 = 7 - 5 = 7 - (26 + (-3)*7) = 4*7 + (-1)*26

1 = 5 - 2*2 = 26 + (-3)*7 - 2(4*7 + (-1)*26) = 3* 26 + (-11)*7

이므로 7x + 26 y = 1의 해를 하나는 (-11, 3)

최대공약수의 부분 기초정리 3의 증명에서 했듯, 7x + 26 y = 4 의 해는 (-44, 12)다. 최소한 하나의 해를 찾았다.

따라서 일반해는 (-44 + 26*m, 12 - 7*m)이다.

 ?

• a, b가 100 (1000, 100000)보다 작은 수들일 때 최대 몇 단계를 거쳐 최대공약수를 찾을 수 있을까? 가능한 가장 작은 수 a,b는? (피보나치 수열과 연관됨)
• a와 b가 직선의 길이를 나타낸다고 할 때, 최대공약수를 찾는 유클리드 알고리듬의 기하학적인 해석은?

자연수 세계 - 서론과 이야기거리 로 돌아가기

Note

Math : Math글쓰기 | Math번역 | MathBoard | Math&Culture | MathMoim
OnLineMathCenter | MathCamp | SoftMathJournal | MathBook | CyberAcademia | Academia