3 최대공약수로 나누기

12와 18의 최대공약수를 구하기 위해 소수로 나누어 보겠습니다. 12와 18의 공약수인 2로 나누었더니 몫이 6과 9가 되었습니다. 다시 6과 9를 3으로 나누었더니 몫이 2와 3이 되었습니다. 이제 공약수가 1밖에 없는 상태이니 멈춥니다. 왼쪽에 쓴 나누는 수는 2와 3이고, 이 수를 곱한 2×3=6이 최대공약수가 됩니다.

 

그런데 나누는 수는 소수가 아니어도 됩니다. 12와 18의 공약수 중에 6으로 나누었더니 계산이 좀 더 짧아졌습니다.