최대공약수는 두 개 이상의 수의 공약수(공통인 약수) 중에서 가장 큰 수를 말한다. 최소공배수는 두 개 이상의 수의 공배수(공통인 배수) 중에서 가장 작은 수를 말한다.
예를 들어 12와 18의 공약수는 1, 2, 3, 6이고, 이 중 가장 큰 6이 최대공약수다. 12와 18의 공배수는 36, 72, 108, ...이고, 이 중 가장 작은 36이 최소공배수다.
최대공약수는 "두 수를 똑같이 나눌 수 있는 가장 큰 덩어리"를 찾는 것이다. 사탕 12개와 초콜릿 18개를 최대한 많은 친구에게 남김없이 똑같이 나눠주려면, 몇 명에게 나눠줄 수 있는지를 구하는 것이 바로 최대공약수를 찾는 문제다.
최소공배수는 반대로 "두 수의 리듬이 처음으로 딱 맞아떨어지는 지점"을 찾는 것이다. 4일마다 도서관에 가는 친구와 6일마다 도서관에 가는 친구가 있다면, 두 친구가 다시 같은 날 도서관에서 만나는 날은 4와 6의 최소공배수인 12일 후다.
이미 알고 있는 약수와 배수로 최대공약수를 구하는 가장 쉬운 방법은, 두 수의 약수를 전부 적어 놓고 겹치는 것을 찾는 것이다. 12와 18로 해 보면 다음과 같다.
그런데 84와 126처럼 수가 커지면 약수를 하나하나 적다가 빠뜨리기 쉽고 시간도 오래 걸린다. 더 빠른 길이 없을까?
두 수를 공약수로 한 번 나누면 무슨 일이 일어나는지 살펴보자. 12와 18을 둘 다 나눌 수 있는 2로 나누면 6과 9가 된다. 6과 9는 아직도 3으로 나눌 수 있으니 나누면 2와 3이 남는다. 이제 2와 3은 1 말고는 공통으로 나눌 수 있는 수가 없다 — 즉 더 쪼갤 수 없는 상태다. 이때 나눈 수들을 모두 곱해 보면
$$2 \times 3 = 6$$
이 되어, 약수를 나열해서 찾은 최대공약수 6과 정확히 같다. 나눌 때마다 두 수에서 "공통으로 들어 있던 부분"을 하나씩 꺼낸 것이므로, 더 이상 꺼낼 것이 없을 때까지 꺼낸 수들을 모두 곱하면 두 수에 공통으로 들어 있던 가장 큰 덩어리, 곧 최대공약수가 된다. 이것이 "공약수로 나누어 구하기" 방법이 통하는 이유다.
이제 최소공배수도 같은 그림에서 찾을 수 있다. 12는 $6 \times 2$, 18은 $6 \times 3$으로 나뉘었고, 남은 2와 3은 더 이상 공통인 수가 없다(서로소). 두 수의 공배수가 되려면 공통 부분 6은 물론이고, 12에만 있는 2와 18에만 있는 3까지 모두 곱해서 가지고 있어야 한다. 그래서 가장 작은 공배수는
$$6 \times 2 \times 3 = 36$$
이 되어, 배수를 나열해서 찾은 최소공배수 36과 같다. 여기서 최대공약수 $G$, 최소공배수 $L$, 두 수 $A=G\times2$, $B=G\times3$ 사이의 관계도 보인다.
$$A \times B = (G\times2)\times(G\times3) = G\times(G\times2\times3) = G \times L$$
실제로 확인해 보면 $12\times18=216$이고 $6\times36=216$으로 같다. 이 관계 덕분에 최대공약수만 구하면 최소공배수는 계산으로 바로 얻을 수 있다.
약수를 나열해서 구하기: 두 수의 약수를 각각 써 보고 공통인 것 중 가장 큰 수를 찾는다.
배수를 나열해서 구하기: 두 수의 배수를 각각 써 보고 공통인 것 중 가장 작은 수를 찾는다.
공약수로 나누어 구하기: 두 수를 공약수로 계속 나누어 가다가 더 이상 공통으로 나눌 수 없을 때, 나눈 공약수들을 모두 곱하면 최대공약수가 된다. 이때 나눈 공약수들과 마지막에 남은 몫을 모두 곱하면 최소공배수가 된다.
두 수를 각각 $A$, $B$라 하고 최대공약수를 $G$라 할 때, 다음 관계가 성립한다.
$$A \times B = G \times (\text{최소공배수})$$
16과 24의 최대공약수와 최소공배수 구하기
16과 24를 공약수로 나누어 보면 다음과 같다.
최대공약수는 나눈 수들을 곱한 값이다: $2 \times 2 \times 2 = 8$
최소공배수는 나눈 수들과 마지막 몫을 모두 곱한 값이다: $2 \times 2 \times 2 \times 2 \times 3 = 48$
확인: $16 \times 24 = 384$이고, $8 \times 48 = 384$로 같다.
버스 정류장에서 A 버스는 15분마다, B 버스는 20분마다 온다고 하자. 두 버스가 동시에 도착한 뒤 다시 동시에 도착하는 시간은 15와 20의 최소공배수인 60분 후다. 반대로 사과 24개와 배 36개를 최대한 많은 바구니에 남김없이 똑같이 나눠 담으려면, 24와 36의 최대공약수인 12바구니에 담으면 된다.
옛날 그리스에서는 땅을 측량하거나 물건을 똑같이 나누는 문제를 풀 때, 두 길이나 두 양을 공통으로 잴 수 있는 가장 큰 단위가 무엇인지 찾아야 했다. 그리스 수학자 유클리드는 기원전 300년경에 쓴 책 원론에서, 두 수를 번갈아 나누어 나머지가 0이 될 때까지 계속하면 최대공약수를 구할 수 있다는 방법을 정리했다. 이 방법은 오늘날 '유클리드 호제법'이라 불리며, 이 문서의 "공약수로 나누어 구하기" 방법과 같은 원리를 담고 있다. 최소공배수는 이후 분수의 통분처럼 서로 다른 수들을 같은 기준으로 맞춰야 하는 계산에서 자연스럽게 함께 쓰이게 되었다.