소인수분해

素因數分解. Prime Factorization.

개요[편집 | 원본 편집]

자연수의 소인수분해(factorization)란 합성수를 소수인 인수(약수)들의 곱으로 나타내는 것이다. ^[1]예를 들면 6=2×3과 같이.

소수를 처음 배우는 초등학교부터 자주는 아니더라도 계속 쓰이는 기본적인 수학 도구. 다만, 소인수분해가 왜 되는지 아는 사람은 수학과를 제외하고 드물다. 모든 합성수가 당연히 소인수분해가 된다고 흔히들 생각하는데, 큰 오산이다. 수학에 공리를 제외하고 당연한 것은 없으며, 모두 수학적인 증명을 요구한다. 이에 대해서는 아래 산술의 기본 정리 부분을 참고하자.

이 소인수분해와 비슷한 개념으로 (다항식의) 인수분해가 있다. 그런데 환에서는 다항식의 인수분해와 구별할 필요가 없기 때문에 둘 다 인수분해라 한다. 어떤 원소를 (소수가 아니라) 기약원(irreducible element)들의 곱으로 나타내는 것을 인수분해라 한다.

산술의 기본 정리[편집 | 원본 편집]

Fundamental Theorem of Arithmetic

“ 1보다 큰 모든 정수 [math]\displaystyle{ n }[/math]은 [math]\displaystyle{ n={p_1}^{e_1}{p_2}^{e_2}\cdots{p_n}^{e_n} }[/math]로 (순서가 바뀐 것을 제외하고) 유일하게 나타낼 수 있다. 단, 여기서 [math]\displaystyle{ e_i\geq0 }[/math]이고, [math]\displaystyle{ p_i }[/math]는 서로 다른 소수이다. “

우리가 소인수분해를 당연하게 여길 수 있게 만들어 주는 정리. 이름이 비슷한 대수학의 기본 정리는 듣기만 해도 정신이 날아갈 듯한 증명을 사용하지만, 이 산술의 기본정리는 ~~좀 아주 많이 똑똑한~~ 초등학생도 증명을 할 수 있다. 증명은 존재성과 유일성, 두 파트로 나뉜다.

존재성[편집 | 원본 편집]

1보다 큰 임의의 양의 정수 [math]\displaystyle{ n }[/math]의 두번째로 작은 약수는 소수여야 한다.^[2] 만약 [math]\displaystyle{ m }[/math]이 [math]\displaystyle{ n }[/math]의 두번째로 작은 약수인데 합성수라면, 합성수의 정의에 의해 [math]\displaystyle{ l\mid m,\,1\lt l\lt m }[/math]인 소수 [math]\displaystyle{ l }[/math]이 존재한다. 그런데 [math]\displaystyle{ m\mid n }[/math]이므로 [math]\displaystyle{ l\mid n }[/math]이고, 이는 [math]\displaystyle{ m }[/math]이 두번째로 작은 약수라는 정의에 모순된다. 따라서 [math]\displaystyle{ m }[/math]은 소수이다. 따라서, [math]\displaystyle{ n=p_1n_1 }[/math]로 표현할 수 있고 ([math]\displaystyle{ p_1=m }[/math]), [math]\displaystyle{ n_1 }[/math]이 소수라면 증명은 끝. 소수가 아니라면 위 과정을 계속 반복하여 [math]\displaystyle{ n }[/math]을 소수의 곱으로만 표현할 수 있다. 즉, 1보다 큰 임의의 양의 정수 [math]\displaystyle{ n }[/math]의 소인수분해가 존재한다.

유일성[편집 | 원본 편집]

증명 1

귀류법을 사용해 증명한다. 집합 [math]\displaystyle{ A }[/math]를 [math]\displaystyle{ A=\left\{x\in\mathbb{N}|x\gt 1, x\right. }[/math]의 소인수분해는 유일하지 않음[math]\displaystyle{ \left.\right\} }[/math]로 정의하자. 자연수의 정렬성에 의해 집합 [math]\displaystyle{ A }[/math]에는 가장 작은 원소가 존재한다.^[3] 이를 [math]\displaystyle{ n }[/math]라 하자. 그럼, [math]\displaystyle{ p_1\leq p_2\leq\cdots\leq p_k,\,q_1\leq q_2\leq\cdots\leq q_l }[/math]을 만족하는 소수 [math]\displaystyle{ p_1,p_2,\cdots,p_k,q_1,q_2,\cdots,q_l }[/math]에 대해 [math]\displaystyle{ n=p_1p_2\cdots p_k=q_1q_2\cdots q_l }[/math]이 성립한다. 여기서 만약 어떤 [math]\displaystyle{ i,j }[/math]에 대해 [math]\displaystyle{ p_i=q_j }[/math]이면, [math]\displaystyle{ n/p_i }[/math]도 소인수분해가 유일하지 않고, [math]\displaystyle{ n\gt n/p_i }[/math]이므로 [math]\displaystyle{ n }[/math]이 [math]\displaystyle{ A }[/math]의 가장 작은 원소라는 사실에 모순된다. 즉, [math]\displaystyle{ p_i\neq q_j }[/math]. 한편, [math]\displaystyle{ {p_1}^2\leq n, {q_1}^2\leq n }[/math]이고 [math]\displaystyle{ {p_1}^2 }[/math]와 [math]\displaystyle{ {q_1}^2 }[/math]은 동시에 [math]\displaystyle{ n }[/math]이 될 수 없으므로,^[4] [math]\displaystyle{ 0\lt p_1q_1\lt n }[/math]이다. 이제 [math]\displaystyle{ N=n-p_1q_1 }[/math]이라 정의하자. [math]\displaystyle{ 0\lt N\lt n }[/math]이고 [math]\displaystyle{ p_1\mid N,\,q_1\mid N }[/math]이므로, [math]\displaystyle{ 1\lt N\lt n }[/math]이 성립하고, [math]\displaystyle{ N }[/math]은 유일한 소인수분해를 가진다.^[5] 또한 [math]\displaystyle{ N }[/math]의 유일한 소인수분해에는 [math]\displaystyle{ p_1 }[/math]과 [math]\displaystyle{ q_1 }[/math]이 둘 다 들어간다. 따라서 적당한 양의 정수 [math]\displaystyle{ M }[/math]에 대해 [math]\displaystyle{ N=p_1q_1M }[/math]. 이제 [math]\displaystyle{ n=N+p_1q_1=p_1q_1\left(M+1\right) }[/math]이고, 양변을 [math]\displaystyle{ p_1 }[/math]로 나누면 [math]\displaystyle{ n/p_1=q_1\left(M+1\right) }[/math]. 곧, [math]\displaystyle{ p_2p_3\cdots p_k=q_1\left(M+1\right) }[/math]이다. 여기서 [math]\displaystyle{ q_1\neq p_i }[/math]이므로 [math]\displaystyle{ n/p_1 }[/math]는 유일하지 않은 소인수분해를 가진다.^[6] 또한 [math]\displaystyle{ 1\lt n/p_1 }[/math]이므로 [math]\displaystyle{ n/p_1\in A }[/math]이고, [math]\displaystyle{ n/p_1\lt n }[/math]이므로 이는 [math]\displaystyle{ n }[/math]이 집합 [math]\displaystyle{ A }[/math]의 가장 작은 원소라는 사실에 모순된다. 따라서 1보다 큰 임의의 양의 정수의 소인수분해는 유일하다.

~~이게 어딜 봐서 초등학생도 할 수 있냐~~

증명 2

[math]\displaystyle{ n = p_1 \cdots p_k = q_1 \cdots q_l }[/math]이 1보다 큰 양의 정수 [math]\displaystyle{ n }[/math]의 두 가지 소인수분해라고 하자(단, [math]\displaystyle{ k,\; l }[/math]은 자연수이고 [math]\displaystyle{ k \leq l }[/math]). [math]\displaystyle{ p_i }[/math]들 그리고 [math]\displaystyle{ q_j }[/math]이 서로 같은지 다른지는 이 증명에서 아무 문제가 안 되기 때문에 거듭제곱 표현을 전부 풀어 적었고, 이렇게 적어도 소인수분해라는 데 이의는 없을 것이다.

이제 [math]\displaystyle{ p_1 | q_1 \cdots q_l }[/math]이고 [math]\displaystyle{ p_1 }[/math]은 소수이므로 소수의 정의에 의해 [math]\displaystyle{ q_1,\; \cdots,\; q_l }[/math] 중 [math]\displaystyle{ p_1 }[/math]로 나누어 떨어지는 것이 있을 것이다. 이를 일반성을 잃지 않고 [math]\displaystyle{ q_1 }[/math]이라 하자. 이제 [math]\displaystyle{ q_1 }[/math]도 소수이므로 역시 소수의 정의에 의해 [math]\displaystyle{ q_1 }[/math]의 양의 약수는 [math]\displaystyle{ 1,\; q_1 }[/math] 둘뿐이다. 따라서 [math]\displaystyle{ p_1=q_1 }[/math]일 수밖에 없다. 따라서 양변에서 [math]\displaystyle{ p_1=q_1 }[/math]을 소거하여 [math]\displaystyle{ p_2 \cdots p_k = q_2 \cdots q_l }[/math]을 얻는다.

이제 [math]\displaystyle{ p_2,\; \cdots,\; p_k }[/math]에 대해 위 과정을 반복하여 최종적으로 [math]\displaystyle{ 1 = q_{k+1} \cdots q_l }[/math]을 얻는다. 그런데 좌변은 약수가 1뿐이므로 위 식의 우변에는 소수가 하나라도 있으면 안 되고, 따라서 [math]\displaystyle{ k=l }[/math]을 얻는다. 나아가 위 반복하는 과정에서 [math]\displaystyle{ p_1=q_1,\; \cdots,\; p_k=q_k }[/math]인 점까지 알 수 있다. 따라서 위 두 개의 소인수분해는 서로 같고, 따라서 소인수분해가 유일함을 알 수 있다.