[수학] 증명: 자연수의 소인수분해와 제곱수 표현

자연수의 소인수분해

모든 자연수는 소인수분해를 통해 소수들의 곱으로 표현할 수 있다. 예를 들어, 720의 경우 다음과 같이 소인수분해할 수 있다.

$$720 = 2^4 \times 3^2 \times 5$$

이는 720이 2, 3, 5라는 소수의 곱으로만 이루어졌음을 보여준다. 이러한 소수들을 소인수(prime factor) 라고 하며, 이 과정을 소인수분해(prime factorization) 라고 한다.

유일한 소인수분해 정리

모든 자연수는 소수의 곱으로 유일하게 표현될 수 있으며, 이를 소인수분해의 유일성(Unique Prime Factorization Theorem) 이라고 한다. 즉, 같은 수를 다른 소수들의 곱으로 표현하는 것은 불가능하다.

증명

이를 증명하기 위해 다음과 같은 가정을 해보자.

1. 소인수분해가 유일하지 않은 가장 작은 자연수 $n$ 을 선택한다.
2. $n$ 을 두 가지 다른 소인수분해 방식으로 표현한다. $$n = p_1 p_2 \dots p_k = q_1 q_2 \dots q_m$$ 여기서 $p_i$ 와 $q_j$ 는 모두 소수이다.
3. $p_1$ 과 $q_1$ 중 하나는 반드시 다른 소인수분해에도 포함되어 있어야 하므로, $p_1 = q_j$ 인 일부 $j$ 가 존재한다.
4. 두 식에서 $p_1$ 을 제거하면, 남은 부분 역시 서로 다른 두 가지 소인수분해를 가지게 되며, 이는 $n$ 보다 작은 자연수에 대한 가정에 모순된다.
5. 따라서 소인수분해는 반드시 유일해야 한다.

자연수의 제곱수 표현

모든 자연수는 다음과 같은 형태로 표현될 수 있다.

$$n = j^2 \times k$$

여기서 $j$ 와 $k$ 는 자연수이며, $k$ 는 제곱인수가 없는 수(square-free number) 이다. 즉, $k$ 의 소인수분해에서 어떤 소수도 2번 이상 곱해지지 않는다.

증명

1. 자연수 $n$ 의 소인수분해를 수행하여 다음과 같이 표현한다. $$n = p_1^{a_1} p_2^{a_2} \dots p_m^{a_m}$$ 여기서 $p_i$ 는 서로 다른 소수들이며, $a_i$ 는 각 소수의 지수이다.
2. $j$ 를 다음과 같이 정의한다. $$j = p_1^{\lfloor a_1 / 2 \rfloor} p_2^{\lfloor a_2 / 2 \rfloor} \dots p_m^{\lfloor a_m / 2 \rfloor}$$ 즉, 각 소수의 지수를 반으로 나눈 값의 정수 부분을 사용하여 $j$ 를 만든다.
3. $k$ 를 다음과 같이 정의한다. $$k = p_1^{a_1 - 2\lfloor a_1 / 2 \rfloor} p_2^{a_2 - 2\lfloor a_2 / 2 \rfloor} \dots p_m^{a_m - 2\lfloor a_m / 2 \rfloor}$$ 즉, $k$ 는 남은 지수 부분을 가지며, 각 $p_i$ 에 대한 지수는 0 또는 1이므로 제곱인수가 없다.
4. 따라서 모든 자연수 $n$ 은 $n = j^2 \times k$ 형태로 표현될 수 있으며, $k$ 는 제곱인수를 가지지 않는다.

결론

자연수의 소인수분해는 유일하며, 이를 이용하면 모든 자연수를 제곱수와 제곱인수가 없는 수의 곱으로 표현할 수 있다. 이는 수론에서 중요한 개념 중 하나이며, 다양한 정리와 증명의 기초가 된다.