최대공약수가 무엇인지는 여러분 모두가 잘 아실겁니다. 

직역하자면 공약수 중에서 가장 큰 공약수이고, 소인수분해 결과 공통된 소수들의 곱으로 나타냅니다. 

예를 들어 45와 18의 최대 공약수는 9입니다.

45와 18을 각각 소인수 분해하면 아래와 같습니다.

, 

여기서 공통되는 공약수 3의 제곱, 9가 최대공약수가 되는 것이죠.

이렇게 소인수분해를 통해서 어떤 숫자들이든 간에 최대공약수를 구할 수 있습니다.

하지만 숫자가 커지면 소인수분해를 직접 하는 것이 번거롭고 실수를 하기 마련입니다. 

그래서 더욱 좋은 방법을 정리하고자 합니다.

바로 유클리드 호제법입니다. 

결론부터 얘기하겠습니다.

두 자연수 a, b의 최대공약수 G(a,b)는 b와 a를 b로 나눈 수의 최대공약수 G(a mod b)와 같다는 점을 이용해 최대공약수를 구하는 것입니다.

이렇게 나머지가 0이 될 때까지 반복해서 나누고 이 때 나누는 수가 처음 두 자연수 a, b의 최대공약수가 되는 것입니다.

조금더 풀어말하자면,

이라고 했을 때  G(a,b) = G(b,r)입니다. 

그리고 G(b,r)은 또 r과 b를 r로 나눈 나머지의 최대공약수와 같게 됩니다.

이렇게 계속 나머지가 0이 될 때까지 나누고 이 때 나누는 수가 최대 공약수가 됩니다.

 예시를 통해 알아보겠습니다!

45와 18의 최대공약수를 구해보자면,

45와 18의 최대공약수는 18과 45를 18로 나눈 나머지인 9 최대공약수와 같습니다.

G(45,18) = G(18, 45 mod 18) = G(18, 9)

18를 9로 나누면 몫이 0이기에 9가 45와 18의 최대공약수가 되겠습니다.

그렇다면, 왜 이런 방식이 적용될 수 있을까? 증명이 궁금합니다.

두 자연수 a, b가 있습니다.

a를 이렇게 나타내보도록 하죠.

그리고 a와 b의 최대공약수 G(a,b)는 k라고 하겠습니다.

그럼 두 자연수 a, b를 최대공약수를 이용해 다시 나타낼 수 있습니다.

m, n은 당연히 서로소여야 합니다.

최대공약수로 나누었기 때문에 m과 n에는 1외에는 어떠한 공약수도 있을 수 없기때문입니다.

만약에 있다면 최대공약수는 k에다가 이 공약수를 곱한 수가 되어야 하겠습니다.

이제 이렇게 최대공약수를 이용해 나타낸 a, b를 1번식에 대입해보겠습니다.

이렇게 되고 식을 r에 대해서 정리하면 이렇게 됩니다.

자 여기서, 다시 한번 상기해보겠습니다.

우리가 증명하고 싶은 것은 G(a,b)가 G(b,r)과 같다는 것입니다.

G(a,b)는 k로 정의를 해놓았습니다.

3번식과 5번식을 보면 b와 r은 각각 k를 약수로 가지고 있습니다.

하지만 k가 최대공약수인지는 확실하지 않습니다.

k가 b와 r의 최대공약수가 되려면 어떤 조건이 필요할까요?

그렇습니다.

n과 m-nq가 서로소여야만 b와 r의 최대공약수가 k가 되게 됩니다.

어떤 두수가 서로소임을 보이기 위해서는 주로 귀류법을 사용합니다.

먼저 n과 m-nq가 서로소가 아니라고 가정합니다.

서로소가 아니기에 둘의 최대공약수를 S라고 하고 각각을 나타내보겠습니다.

n을 오른쪽의 식에 대입합니다.

식을 정리합니다.

어떻습니까?

3번식에서 우리는 m과 n이 서로소임을 밝혔습니다.

하지만 지금, n과 m-nq가 서로소가 아니라고 가정했을 때 m과 n이 서로소입니까?

m과 n이 S라는 최대공약수를 가지고 있기 때문에 서로소가 아니게 되고 이는 원래 식과 모순을 일으키게 됩니다.

이는 n과 m-nq는 서로소임을 간접적으로 증명하게 됩니다.

이 두수가 서로소가 되었음으로 b와 r의 최대공약수도 k가 되는 것을 확인하게 되었습니다.