소인수분해


素因數分解. Prime Factorization.

1 개요[편집]

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

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

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

2 산술의 기본 정리[편집]

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]는 서로 다른 소수이다.

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

2.1 존재성[편집]

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]의 소인수분해가 존재한다.

2.2 유일성[편집]

  • 증명 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]인 점까지 알 수 있다. 따라서 위 두 개의 소인수분해는 서로 같고, 따라서 소인수분해가 유일함을 알 수 있다.

3 소인수분해를 하는 방법[편집]

이 문단에서는 1보다 큰 어떤 정수 [math]\displaystyle{ N }[/math]이 주어졌을 때, 약수를 찾는 여러 가지 기술에 대해 소개한다. 먼저 가장 쉬운 방법은 아래의 배수 판정법을 이용하는 것이다.

정수 [math]\displaystyle{ N }[/math]에 대해서,

  • 2의 배수: 끝자리가 짝수.
  • 3의 배수: 각 자릿수의 합이 3의 배수.
  • 4의 배수: 맨 뒤 두자리가 4의 배수.
  • 5의 배수: 끝자리가 0이나 5.
  • 6의 배수: [math]\displaystyle{ N }[/math]이 2의 배수이면서 3의 배수.
  • 8의 배수: 맨 뒤 세자리가 8의 배수.
  • 9의 배수: 각 자릿수의 합이 9의 배수.
  • 10의 배수: 끝자리가 0.
  • 7, 11, 13의 배수: 일의 자리부터 세 자리씩 끊은 뒤, 각 부분을 교대로 빼고 더한 값이 7, 11, 13의 배수.[7][8]

아래 정리를 사용할 수도 있다.

모든 합성수는 그 수의 제곱근보다 작거나 같은 약수를 같는다.

증명은 아래와 같다.

[math]\displaystyle{ n }[/math]을 합성수라 하자. 그러면 [math]\displaystyle{ n=ab,\,1\lt a,b\lt n }[/math]이다. 만약 [math]\displaystyle{ a,b }[/math]가 둘 다 [math]\displaystyle{ \sqrt n }[/math]보다 크다면, [math]\displaystyle{ n=\sqrt n\sqrt n\lt ab=n }[/math]이 되어 모순이다. 따라서 [math]\displaystyle{ a,b }[/math]중 적어도 하나는 [math]\displaystyle{ \sqrt n }[/math]보다 작다.

이 정리에 의해 어떤 큰 수를 소인수분해 할 때, 그 수의 제곱근 보다 큰 수로 나눌 필요는 없다는 사실을 알 수 있다. 이는 노가다를 통해 소인수분해를 하는 시간을 크게 단축시켜 준다.

4 관련 항목[편집]

5 각주

  1. 합성수가 아니어도 상관은 없지만 그러면 소인수분해를 하는 의미가 없어진다.
  2. 제일 작은 약수는 당연히 1이다.
  3. 정확히는 [math]\displaystyle{ A }[/math]가 공집합이 아니어야 존재한다. 헌데 [math]\displaystyle{ A }[/math]가 공집합이면 1보다 큰 모든 정수의 소인수분해가 유일함을 의미하게 된다.
  4. 만약 둘이 동시에 [math]\displaystyle{ n }[/math]이면 [math]\displaystyle{ p_1=q_1 }[/math]이고, 이는 위의 [math]\displaystyle{ p_i\neq q_j }[/math]에 모순된다.
  5. 유일하지 않으면 [math]\displaystyle{ N\in A }[/math]이고, 이는 [math]\displaystyle{ n }[/math][math]\displaystyle{ A }[/math]의 가장 작은 원소라는 사실에 모순이다.
  6. [math]\displaystyle{ M+1 }[/math]이 어떻게 소인수분해 되는가와는 상관없다.
  7. 123456789를 예시로 들면, 123-456+789=456이 7의 배수가 아니므로 원래 수는 7의 배수가 아니다. 59255924를 예시로 들면, 59-255+924=728이 7의 배수이므로 원래 수는 7의 배수이다.
  8. 이 방법은 1001=7*11*13 임을 이용한 방법이다. 이 외에도 다른 방법들이 있다.