산술의 기본 정리

산술의 기본 정리는 1보다 큰 모든 자연수를 소수의 곱으로 단 한 가지 방법으로 나타낼 수 있다는 정리이다. 예를 들어 15는 두 소수의 곱 3 · 5로, 30은 세 소수의 곱 2 · 3 · 5로, 16은 네 소수의 곱 2 · 2 · 2 · 2로 나타낼 수 있다. 이런 곱을 소인수분해라고 한다. 그래서 10을 소인수분해하면 2 · 5라고 말한다.

소인수분해가 가장 간단한 수는 소수 자신이다. 더 이상 분해할 필요가 없기 때문이다. 7을 소인수분해하면 그냥 7이다.

소인수분해 계산하기

산술의 기본 정리가 말하는 것

산술의 기본 정리(학교에서는 흔히 소인수분해의 유일성이라고 한다)는 두 가지를 말해 준다.

• 1보다 큰 모든 자연수는 소인수분해할 수 있다.
• 모든 수의 소인수분해는 단 한 가지뿐이다.

정말 그런지 증명해 보자.

존재성의 증명

먼저 1보다 큰 모든 자연수에 소인수분해가 적어도 하나 있다는 것을 증명한다. 이를 위해 수학적 귀납법을 쓴다. 수학적 귀납법의 첫 단계로, 1보다 큰 가장 작은 자연수인 2가 소수라는 것을 확인한다.

이제 소인수분해할 수 있는 수들의 수열 2, …, n이 있을 때, 이 수열에 n + 1을 덧붙이면 이 새로운 수도 소인수분해할 수 있다는 것을 보인다. 먼저 예를 들어 보자.

처음에는 수열 2, …, n이 조금 이상하다. 수가 2 하나뿐이기 때문이다. 이 수열에 n + 1, 즉 3을 덧붙이면 3도 소인수분해할 수 있다고 말한다. 3은 소수이므로 당연히 소인수분해할 수 있고, 그 소인수분해는 3 자신이다.

이제 수열 2, …, n은 두 항 2, 3으로 이루어진다. 수열에 4를 덧붙이자. 4는 소수가 아니므로, 1보다 크고 4보다 작은 두 자연수의 곱으로 나타낼 수 있어야 한다. 그런데 그런 수는 모두 앞의 수열에 들어 있다! 게다가 이 수열에는 소인수분해할 수 있는 수만 들어 있다! 따라서 4도 2 · 2로 소인수분해할 수 있어야 한다.

일반적인 증명으로 돌아가면 다음과 같이 쓸 수 있다. 2는 소수이므로 소인수분해할 수 있다. 이제 수열 2, …, n의 모든 수를 소인수분해할 수 있다고 가정하자. 이것이 귀납 가정이다. 그러면 n + 1은 소수이거나(이때는 당연히 소인수분해할 수 있다) 합성수이다. 합성수라면 다음을 만족하는 수 a, b가 있어야 한다.

$$n+1=a\cdot b$$

이때 두 자연수는 당연히 n + 1보다 작고 1보다 커야 한다.

$$\begin{array}{rcl}a>1,& & a<n+1\\ b>1,& & b<n+1\end{array}$$

따라서 a, b는 수열 2, …, n에 들어 있어야 한다. 그런데 이 수열의 모든 수는 소인수분해할 수 있으므로(귀납 가정), 다음과 같이 쓸 수 있다.

$$\begin{array}{rcl}a& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ b& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

여기서 p_i와 q_j는 모두 소수이고, p₁ · p₂ · … · p_i와 q₁ · q₂ · … · q_j는 두 수의 소인수분해이다. 그런데 n + 1은 곱 n + 1 = a · b로 나타낼 수 있다고 했으므로, 다음도 성립한다.

$$\begin{array}{rcl}n+1& =& a\cdot b\\ & =& p_1\cdot p_2\cdot \dots \cdot p_i\cdot q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

따라서 n + 1은 소수의 곱 p₁ · p₂ · … · p_i · q₁ · q₂ · … · q_j로 나타낼 수 있다. 즉 새로 덧붙인 수 n + 1도 소인수분해할 수 있다. 이로써 1보다 큰 모든 자연수는 소인수분해가 적어도 하나 있다.

유일성의 증명

이제 1보다 큰 어떤 자연수도 소인수분해가 여러 가지일 수 없다는 것을 보이자. 이 정리는 귀류법으로 증명한다. 정리가 참이 아니라고 가정하자. 즉 소인수분해가 서로 다른 두 가지인, 1보다 큰 자연수 n이 있다고 가정한다.

$$\begin{array}{rcl}n& =& p_1\cdot p_2\cdot \dots \cdot p_i\\ n& =& q_1\cdot q_2\cdot \dots \cdot q_j\end{array}$$

또 소인수분해가 여러 가지인 수 가운데 n이 가장 작은 수라고 가정한다. 즉 이보다 작은 자연수 가운데 소인수분해가 둘 이상인 수는 없다. q₁은 n을 나누는 소수 가운데 하나이므로, 당연히 q₁은 p₁ · p₂ · … · p_i도 나누어야 한다.

다음으로 유클리드의 보조정리를 써야 한다. 이 보조정리에 따르면 소수 p가 두 정수의 곱 a · b를 나누면 p는 a와 b 가운데 적어도 하나를 나눈다. 예를 들어 소수 3은 84를 나눈다. 84는 곱 12 · 7로 나타낼 수 있다. 유클리드의 보조정리에 따르면 소수 3은 12와 7 가운데 적어도 하나를 나눈다. 이 경우에는 12를 나눈다.

이 보조정리를 쓰면, q₁이 p₁ · p₂ · … · p_i를 나누므로 p₁, p₂, …, p_i 가운데 적어도 하나를 나누어야 한다. 일반성을 잃지 않고 q₁이 p₁을 나눈다고 가정할 수 있다. 그런데 p₁도 소수이다. 소수가 다른 소수를 나눌 수 있는 것은 언제일까? 예를 들어 소수 7로 나누어떨어지는 소수는 무엇일까? 역시 7뿐이다. 다른 소수를 나눌 수는 없다. 그렇다면 그 수는 소수가 아닐 것이기 때문이다. 따라서 p₁ = q₁이어야 한다.

즉 두 소인수분해에는 같은 소수가 하나 있다. 그 소수는 p₁, 다시 말해 q₁이다. 두 식의 양변을 각각 p₁과 q₁로 나누자.

$$\begin{array}{rcl}\frac{n}{p_1}& =& \frac{p_1\cdot p_2\cdot \dots \cdot p_i}{p_1}\\ \frac{n}{q_1}& =& \frac{q_1\cdot q_2\cdot \dots \cdot q_j}{q_1}\end{array}$$

p₁ = q₁이므로 좌변은 같은 수가 된다. 이 수를 m이라고 하자. 그러면 다음이 성립한다.

$$m=\frac{n}{p_1}=\frac{n}{q_1}$$

우변은 분수를 약분하기만 하면 된다.

$$\begin{array}{rcl}m& =& p_2\cdot p_3\cdot \dots \cdot p_i\\ m& =& q_2\cdot q_3\cdot \dots \cdot q_j\end{array}$$

m은 분명히 n보다 작은 자연수이다. m은 n을 소인수 하나로 나누어 얻은 수이기 때문이다. 그런데 두 식의 우변은 모두 m의 소인수분해이다. 즉 n보다 작으면서 소인수분해가 서로 다른 두 가지인 수 m을 만들어 냈다. 이는 n이 소인수분해가 둘 이상인 가장 작은 수라는 가정에 모순이다.

따라서 유일하게 가능한 설명은 “소인수분해가 둘 이상인 가장 작은 수”가 없다는 것이다. 그리고 “소인수분해가 둘 이상인 가장 작은 수”가 없다는 것은 소인수분해가 여러 가지인 수가 하나도 없다는 뜻이다. 즉 1보다 큰 모든 정수의 소인수분해는 단 한 가지뿐이다.