도전 과제 : 유클리드 호제법

본 자료는 인공지능을 활용하지 않고 작성되었음을 알립니다.

Euclidean Algorithm

소개

소인수분해의 과정 (출처: 천재교육)

큰 수를 소인수분해하는 것은 컴퓨터로 다루기에도 상당히 어려운 문제이다.

아래의 상황을 생각해보자.

\[20677와\;15341의\;최대공약수를\;구하시오.\]

수가 커지니 문제가 상당히 복잡하게 느껴진다. 위 경우에서 두 수의 가장 작은 공통 소인수는 $23$인데, $2, 3, 5, 7, \dots$ 이런 식으로 $23$까지 일일이 나눠 본 다음에서야 공통 소인수를 겨우 하나 찾을 수 있다는 것은 상당히 절망스럽다. 이처럼 수가 조금만 커져도 소인수분해의 난이도는 급격하게 어려워진다는 것을 확인할 수 있다.

만약 소인수분해가 이렇게나 어려워진다면,

최대공약수를 구할 때 반드시 소인수분해를 해야 하나?

라는 의문을 가져볼 수 있다. 만약에 창의적인 알고리즘(algorithm)을 떠올려서 각각의 수를 소인수분해하지 않고도 최대공약수를 구할 수 있다면 어떨까?

소인수분해나 최대공약수의 개념을 처음 접하는 사람이라면 이것이 어떻게 가능한지 이해가 가지 않을 수도 있다. 필자 역시도 유클리드 호제법을 처음 배웠을 때는 개념이 잘 이해가 가지 않아 어려워했던 기억이 있다. 하지만 쉽게 설명한다면 생각보다 어렵지 않게 이해할 수 있는 내용이니 한 번 살펴보자.

유클리드 호제법 (Euclidean Algorithm)

유클리드 호제법과 타일 채우기 (출처: senalyst.com)

두 자연수 $A, B$를 생각하자. $A$를 $B$로 나눌 때 몫(quotient)을 $Q$, 나머지(remainder)를 $R$이라고 하면

\[\textrm{gcd}(A,B)=\textrm{gcd}(B,R)\]

이다. 단, $A \ge B$이고 $\textrm{gcd}(a, b)$는 $a$와 $b$의 최대공약수를 의미한다.

예시를 살펴보자. $8$와 $22$의 최대공약수를 구하고 싶다면

$22$을 $8$로 나눈 몫은 $2$, 나머지는 $6$ → $\textrm{gcd}(22, 8)=\textrm{gcd}(8,6)$

$8$을 $6$으로 나눈 몫은 $1$, 나머지는 $2$ → $\textrm{gcd}(8, 6) = \textrm{gcd}(6,2)$

$6$을 $2$로 나눈 몫은 $3$, 나머지는 $0$ → $\textrm{gcd}(8, 6) = \textrm{gcd}(2, 0)$

모든 수는 $0$의 약수이기에 $\textrm{gcd}(2,0)=2$이다. 따라서 $8$과 $22$의 최대공약수는 $2$이다.

유클리드 호제법의 시각화

$60 \times 24$ 벽면을 남김없이 채우기 위한 정사각형 타일의 최대 크기는?

유클리드 호제법을 그림을 통해서 알아보자. 위의 타일 채우기 문제에서, 우리는 이미 타일 한 변의 길이가 곧 채워야하는 벽면의 가로 길이와 세로 길이의 최대공약수라는 것을 알고 있다.

https://www.geogebra.org/m/ztbesvsd

위 링크를 클릭하면 David Wees님께서 유클리드 호제법을 알기 쉽게 타일 채우기로 설명해놓은 것을 확인할 수 있다. 직접 슬라이더로 a와 b의 값을 바꿔가며 유클리드 호제법이 가지는 기하학적 의미에 대해 탐구해보자.

유클리드 호제법의 증명

유클리드 호제법은 아래와 같이 증명할 수 있다.

$\textrm{gcd}(A,B)=G$라고 하면

\[A=Ga,\;B=Gb\;(a,b는\;서로소인\;두\;자연수)\]

이다. $A=BQ+R$이라고 하자. 이때,

\[R=A-BQ=Ga-GbQ=G(a-bQ)\]

이므로, $B$와 $R$은 $G$를 공약수로 가진다. 이제 증명해야 하는 것은 $G$가 최대공약수가 된다는 것인데, 이를 위해 $b$와 $a-bQ$가 서로소임을 보이면 충분하다. 귀류법을 사용하자. 만약 결론을 부정하여

\[\textrm{gcd}(b,a-bQ)=k\;(k는\;1보다\;큰\;자연수)\]

라고 하면,

\[\begin{align*} b=kb'\;(b'는\;자연수)\\ a-bQ=kc\;(c는\;자연수) \end{align*}\]

여기서 $a$와 $b$를 살펴보면

\[\begin{aligned} a&=bQ+kc\\&=kb'Q+kc\\&=k(b'Q+c)\\ b&=kc \end{aligned}\]

$a,b$는 서로소여야하는데, $a$와 $b$의 $1$보다 큰 공약수 $k$가 존재하기 때문에 모순이다.

근데 이게 왜 좋죠?

IBM사의 슈퍼컴퓨터 Summit (출처: ibm.com)

유클리드 호제법을 처음 배울 때 소인수분해가 훨씬 편하다고 생각하는 경우들이 많이 있다. 이런 경우는 대부분 큰 수의 나눗셈이 익숙하지 않은 경우라고 할 수 있다. 하지만 앞서 살펴 본 예시와 같이, 큰 소수가 많이 곱해져 있는 수들의 경우 소인수분해하기가 점점 어려워진다.

일반적으로, 소인수분해하고자 하는 수의 자릿수가 두 개 늘어날 때마다 컴퓨터가 그 수를 소인수분해하는데 걸리는 시간은 약 $10$배씩 늘어난다. 즉, $100$자리 수를 소인수분해하다가 $200$자리 수를 소인수분해하면 시간이 약

\[10^{50}배=100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000배\]

로 오래 걸리는 것이다! 이 정도면 슈퍼컴퓨터로 연산한다고 해도 맥을 못추는 것이 당연하다. 우주의 나이보다 오래 걸리는 작업을 슈퍼컴퓨터한테 시키면 아무리 슈퍼컴퓨터라도 좋아할 리가 없다.

하지만 유클리드 호제법의 경우, 자릿수에 비례하는 시간이 걸리기 때문에 해봤자 $(어떤\;상수)\times 100$ 만큼의 시간이 더 걸릴 뿐이다. 따라서 유클리드 호제법으로 최대공약수를 구하면 훨씬 쉽게 연산을 처리할 수 있다.

즉, 유클리드 호제법을 사용하면 큰 수를 소인수분해하는 문제보다 큰 수들의 최대공약수를 구하는 것이 오히려 더 쉽다!