최대공약수 구하는 법

이전 글에서 서로 다른 두 자연수의 공통된 약수 중에서, 가장 큰 수를 최대공약수라고 부른다 했었는데, 이번에는 최대공약수 구하는 법을 알아보자. 일단 최대공약수를 구하는 방법은 크게 2가지가 있는데, 하나는 “동시에 나눠주는 방법”이고, 또 다른 하나는 “소인수분해를 활용한 방법”이다.

그럼 먼저 “동시에 나눠주는 방법”에 대해서 알아보면, 일단 최대공약수는 두 자연수의 공통된 약수이므로, 동시에 나눠줄 수가 있다. 예를 들어 84와 120의 최대공약수를 구한다고 할 때, 84와 120은 2로 동시에 나눠줄 수가 있다. 그래서 먼저 2로 나눠준다. 그럼 42와 60이 나오는데, 또 2로 나눠줄 수가 있으므로 2로 나눠준다. 이렇게 동시에 나눠줄 수 없을 때까지 계속 나눠주면, 최대공약수를 구할 수 있다.(나눠줄 때는 꼭 소수로 나눠주지 않아도 된다. 그래서 그냥 처음부터 4나 6으로 나눠줘도 상관은 없다)

 

다음으로 “소인수분해를 활용한 방법”에 대해서 알아보면, 일단 위와 마찬가지로 84와 120의 최대공약수를 구한다고 할 때, 먼저 84와 120을 소인수분해한다. 그럼 84=2²×3×7이 나오고 120=2³×3×5가 나오는데, 여기에서 공통된 소수를 찾으면 된다. 왜냐하면 최대공약수는 두 자연수의 공통된 약수이기 때문인데, 이 공통된 소수가 곧 최대공약수이다.(공통된 소수 중에서, 거듭제곱이 작은 걸 선택하면 된다) 그런데 소인수분해를 활용한 방법은 조금 헷갈릴 수가 있다. 그래서 동시에 나눠주는 방법이 더 편할 수도 있지만, 소인수분해를 활용한 문제가 많이 나오므로 알아둬야 한다.