틴매일경제

게티이미지뱅크

저번 시간에 배수에 관한 이야기를 다루면서 7의 배수를 쉽게 찾는 법에 대한 증명을 미루어두었습니다. 7의 배수를 찾는 방법 중에 직접 나누지 않고 알아보는 방법 중 하나를 설명했는데요. 주어진 숫자를 뒤에서부터 순서대로 세 자리씩 나눈 후에, 더하고 빼고를 반복해서 나온 수가 7의 배수인지 확인하는 방법을 설명했습니다. 아래 그림을 보면서 다시 한번 확인해봅시다.

이 방법은 1001이 7의 배수라는 성질을 이용한 것입니다. 다음 그림을 보면서 이해해보도록 합시다.

1001을 소인수분해하면 1001=7×11×13입니다. 그러니까 1001은 7의 배수이면서 동시에 11의 배수, 13의 배수라고 할 수 있어요. 따라서 11의 배수와 13의 배수를 찾을 때도 같은 방법을 적용할 수 있답니다.

지난 주제가 배수였으니 이번에는 약수를 다루어보겠습니다. 약수는 어떤 정수를 나누어떨어지게 하는 정수를 말합니다. 음수인 약수도 물론 존재하지만, 교육과정에서 약수는 양수만으로 약속하기 때문에 이번에 다루는 약수들도 모두 양수들로 생각하도록 하겠습니다.

12의 약수는 1, 2, 3, 4, 6, 12 이렇게 6개가 있고, 30의 약수는 1, 2, 3, 5, 6, 10, 15, 30으로 총 8개가 존재합니다. 12와 30의 약수 중 공통으로 있는 숫자는 1, 2, 3, 6이고 우리는 이 수들을 공약수라고 부릅니다. 공약수 중에 가장 큰 수를 최대공약수라고 부르는데 12와 30의 최대공약수는 6이라고 할 수 있습니다. 그리고 12와 30의 공약수들은 최대공약수인 6의 약수들인 것을 확인할 수 있습니다.

일반적으로 두 수의 최대공약수를 구할 때는 소인수분해를 해서 공통인수를 찾아내는 방법을 주로 사용합니다. 위에서 본 12와 30의 공약수를 다시 구해보면 12=2²×3, 30=2×3×5이므로 2×3이 최대공약수라고 할 수 있습니다.

숫자들이 소인수분해하기 힘들게 생겼을 때는 어떻게 공약수를 구할 수 있을까요. 어떤 두 숫자를 A와 B라고 해봅시다. A를 B로 나누었을 때, 나머지를 R이라고 하면 A와 B의 최대공약수는 B와 R의 최대공약수와 같다는 특징을 이용하는 것이 오늘의 주제인데요. 방금 다루었던 12와 30으로 다시 시작해봅시다.

30을 12로 나눈 나머지는 6입니다. 그래서 우리는 30과 12가 아닌, 12와 6의 공약수를 구하면 되는데요. 12는 6으로 나누어떨어지므로 처음 두 수인 30과 12의 최대공약수는 6이라고 할 수 있습니다.

조금 더 복잡한 예시인 18564와 630의 최대공약수를 구하면서 더 알아봅시다. 다음 내용을 읽기 전에 두 수의 최대공약수를 직접 구해보는 것도 여러분의 계산 실력에 도움이 될 것입니다. 18564를 630으로 나누면 나머지가 294입니다. 그래서 우리는 630과 294의 최대공약수를 구하면 되는 것입니다. 얻어낸 두 수를 방금 했던 방법으로 계속 진행해 나갑니다. 630을 294로 나누면 나머지가 42이므로 우리가 가진 두 수는 294와 42입니다. 294는 42로 나누어떨어집니다. 마지막에 나누어떨어지게 만든 42가 처음 18564와 630의 최대공약수라고 할 수 있습니다.

위와 같은 방식으로 최대공약수를 구하는 방법은 기원전 3세기에 유클리드라는 수학자가 쓴 책에 담겨 있습니다. 그리고 그의 이름을 따서 유클리드 호제법이라고 부르는데요. 호제법(互除法)은 서로 나누는 방법이라는 뜻입니다. 간단하게 원리를 살펴보겠습니다.

A, B 두 수가 서로 최대공약수인 G(GCD·Greatest Common Divisor)를 가지고 있을 때, A에서 B에 어떤 정수를 곱해서 빼도 항상 G라는 약수를 가지고 있다는 것을 응용한 것입니다.

고등학교 과정만 가더라도 두 수의 최대공약수를 구하는 과정 자체를 묻는 문제가 거의 없고 만약 나온다고 하더라도 구하기가 힘든 경우는 거의 없을 것입니다. 초등학교, 중학교 과정에서는 최대공약수를 구하는 문제들이 종종 있고, 그럴 때 평소에 쓰던 방식 이외에 이런 방법을 사용해보는 것도 나쁘지 않을 것입니다.