들어가며
초등학교에서 최대공약수(GCD)와 최소공배수(LCM)를 구할 때 '약수를 일일이 나열해서 비교'하는 방법을 배웁니다. 그런데 숫자가 커지면 그 방법은 금세 한계에 부딪히죠.
"소수가 수의 원자라고요? 그게 최대공약수·최소공배수랑 무슨 상관인가요?"
한 줄로 답하면: 모든 자연수는 소수의 곱으로 단 한 가지 방법으로만 분해되고, 그 분해에서 지수의 최솟값을 뽑으면 최대공약수, 최댓값을 뽑으면 최소공배수가 됩니다. 그리고 최솟값 + 최댓값 = 원래 지수의 합이라서, 최대공약수 × 최소공배수 = A × B라는 등식이 저절로 따라 나옵니다.
소수란 무엇인가 — 수의 원자
소수(prime number)는 1과 자기 자신으로만 나눠지는, 2 이상의 자연수입니다. 2, 3, 5, 7, 11, 13, … 이 수들은 더 이상 잘게 쪼갤 수 없는 수의 원소입니다.
물질이 원자로 이루어지듯, 모든 자연수는 소수의 곱으로 이루어집니다. 예를 들어:
$$12 = 2 \times 2 \times 3 = 2^2 \times 3^1$$$$18 = 2 \times 3 \times 3 = 2^1 \times 3^2$$여기서 2와 3이 '원자'이고, \(2^2 \times 3^1\)과 \(2^1 \times 3^2\)가 각 수의 '분자 구조'에 해당합니다. 지수가 몇 번씩 어떤 소수를 담고 있는지가 그 수의 정체를 전부 말해줍니다.
산술의 기본 정리 — 소인수분해는 단 하나뿐
1보다 큰 모든 자연수는 소수의 곱으로 단 한 가지 방법으로만 분해됩니다.
이것이 '산술의 기본 정리(Fundamental Theorem of Arithmetic)'입니다. '유일하다'는 점이 핵심입니다.
12를 예로 들면, 어떤 순서로 나눠도 결국 \(2^2 \times 3\)으로 끝납니다. \(2 \times 6\)으로 시작하든 \(3 \times 4\)로 시작하든, 소수 잎까지 내려가면 항상 같은 조각들이 남습니다. 이 '유일성' 덕분에 소수 지수들이 두 수를 비교하는 공통 언어가 됩니다.
소인수 지수에서 최대공약수가 나오는 방법
두 수 12와 18의 소인수분해를 나란히 적어봅니다.
$$12 = 2^2 \times 3^1, \qquad 18 = 2^1 \times 3^2$$최대공약수(GCD)는 두 수를 모두 나눌 수 있는 가장 큰 수입니다. 소수 원자 단위로 보면, 두 수에 공통으로 들어있는 만큼 — 즉 각 소인수 지수의 최솟값 — 만 꺼낼 수 있습니다.
- 소인수 2: 12에 \(2^2\), 18에 \(2^1\) → 공통으로는 \(2^{\min(2,1)} = 2^1\)
- 소인수 3: 12에 \(3^1\), 18에 \(3^2\) → 공통으로는 \(3^{\min(1,2)} = 3^1\)
따라서:
$$\gcd(12, 18) = 2^1 \times 3^1 = 6$$소인수 지수에서 최소공배수가 나오는 방법
최소공배수(LCM)는 두 수를 모두 담을 수 있는 가장 작은 수입니다. 12도, 18도 각각 나눠야 하므로, 어느 쪽이든 더 많이 쓴 소인수를 전부 포함해야 합니다. 즉 각 소인수 지수의 최댓값을 가져옵니다.
- 소인수 2: \(2^{\max(2,1)} = 2^2\) 필요 (12의 \(2^2\)를 수용하려면)
- 소인수 3: \(3^{\max(1,2)} = 3^2\) 필요 (18의 \(3^2\)를 수용하려면)
따라서:
$$\text{lcm}(12, 18) = 2^2 \times 3^2 = 4 \times 9 = 36$$최대공약수 × 최소공배수 = A × B — 왜 항상 성립하나
각 소인수별로 최솟값과 최댓값을 함께 보면 한 가지 사실이 드러납니다.
| 소인수 | A(12)의 지수 | B(18)의 지수 | 최솟값(GCD 기여) | 최댓값(LCM 기여) | 합계 |
|---|---|---|---|---|---|
| 2 | 2 | 1 | 1 | 2 | 3 |
| 3 | 1 | 2 | 1 | 2 | 3 |
각 소인수마다 '최솟값 + 최댓값 = A의 지수 + B의 지수'가 성립합니다. 따라서:
$$\gcd \times \text{lcm} = (2^1 \times 3^1) \times (2^2 \times 3^2) = 2^{1+2} \times 3^{1+2}$$$$A \times B = (2^2 \times 3^1) \times (2^1 \times 3^2) = 2^{2+1} \times 3^{1+2}$$두 식의 지수가 완전히 같아서 결과도 같습니다.
$$\gcd(12, 18) \times \text{lcm}(12, 18) = 6 \times 36 = 216 = 12 \times 18$$이 논리는 어떤 두 자연수를 골라도 똑같이 적용되므로, 등식은 항상 성립합니다.
직접 체험하기
아래에서 두 수를 고르면 소인수별 블록 탑이 그려집니다. 금색 블록은 두 탑이 겹치는 부분(최대공약수 기여), 파란 블록은 A만의 기여, 초록 블록은 B만의 기여입니다. 최대공약수는 겹치는 블록의 곱이고, 최소공배수는 각 소인수에서 더 높은 탑의 곱입니다. 어떤 두 수를 골라도 황금 등식이 성립하는 것을 확인해 보세요.
마치며
소수는 단순히 "약수가 1과 자신뿐인 수"가 아니라, 모든 자연수를 구성하는 유일한 원자 집합입니다. 산술의 기본 정리가 그 분해를 유일하게 만들기 때문에, 소인수 지수들이 두 수의 공통 언어가 됩니다.
- 지수의 최솟값을 소인수별로 뽑아 곱하면 → 최대공약수
- 지수의 최댓값을 소인수별로 뽑아 곱하면 → 최소공배수
- 최솟값 + 최댓값 = 지수의 합 → 최대공약수 × 최소공배수 = A × B
약수를 일일이 나열하는 방법이 왜 우회로였는지, 이제 보이실 겁니다.
함께 보면 좋은 글 — 수는 왜 자연수에서 복소수까지 계속 넓어졌나 (소수가 속한 자연수 ℕ에서 수의 집이 넓어지는 큰 그림) · 로그는 왜 곱셈을 덧셈으로 바꿀까 (소인수분해의 곱이 로그에서 덧셈으로 바뀌는 같은 패턴)