Prime Factorization
1 개요
합성수를 소수들의 곱으로 나타내는 것을 말한다.[1] 소수#s-3를 처음 배우는 중학교부터 자주는 아니더라도 계속 쓰이는 기본적인 수학 도구. 다만, 소인수분해가 왜 되는지 아는 사람은 수학과를 제외하고 드물다. 모든 합성수가 당연히 소인수분해가 된다고 흔히들 생각하는데, 큰 오산이다. 수학에 공리를 제외하고 당연한 것은 없으며, 모두 수학적인 증명을 요구한다. 산술의 기본정리 문서 참고.
'소인수분해'라는 명칭은 중학교에 가서야 언급되지만, 초등학교 때에도 약수와 배수를 구하기 위해 잠시 사용되기는 한다.
2 소인수분해를 하는 방법
이 문단에서는 1보다 큰 어떤 정수 [math]N[/math]이 주어졌을 때, 약수를 찾는 여러가지 기술에 대해 소개한다. 먼저 가장 쉬운 방법은 아래의 배수 판정법을 이용하는 것이다.
정수 [math]N[/math]에 대해서,
1. 2의 배수: 끝자리가 짝수.
1. 3의 배수: 각 자릿수의 합이 3의 배수.
1. 4의 배수: 맨 뒤 두자리가 00 또는 4의 배수.
1. 5의 배수: 끝자리가 0이나 5.
1. 6의 배수: [math]N[/math]이 2의 배수이면서 3의 배수.
1. 8의 배수: 맨 뒤 세자리가 000 또는8의 배수.
1. 9의 배수: 각 자릿수의 합이 9의 배수.
1. 10의 배수: 끝자리가 0.
1. 7, 11, 13의 배수: 일의 자리부터 세 자리씩 끊은 뒤, 각 부분을 교대로 빼고 더한 값이 7, 11, 13의 배수.[2][3][4]
1. 25의 배수: 맨 뒤 두자리가 00 또는 25의 배수(25, 50, 75)
아래 정리를 사용할 수도 있다.
모든 합성수는 그 수의 제곱근보다 작거나 같은 약수를 갖는다.
증명은 아래와 같다.
[math]n[/math]을 합성수라 하자. 그러면 [math]n=ab,\,1\lta,b\ltn[/math]이다. 만약 [math]a,b[/math]가 둘 다 [math]\sqrt n[/math]보다 크다면, [math]n=\sqrt n\sqrt n\ltab=n[/math]이 되어 모순이다. 따라서 [math]a,b[/math]중 적어도 하나는 [math]\sqrt n[/math]보다 작다.
이 정리에 의해 어떤 큰 수를 소인수분해 할 때, 그 수의 제곱근 보다 큰 수로 나눌 필요는 없다는 사실을 알 수 있다. 이는 노가다를 통해 소인수분해를 하는 시간을 크게 단축시켜 준다.
3 관련 문서
- ↑ 합성수가 아니어도 상관은 없지만 그럼 아무 의미가 없어진다.
- ↑ 123456789를 예시로 들면, 123-456+789=456이 7의 배수가 아니므로 원래 수는 7의 배수가 아니다. 59255924를 예시로 들면, 59-255+924=728이 7의 배수이므로 원래 수는 7의 배수이다.
- ↑ 이 방법은 1001=7*11*13, 999999=33*37*1001 임을 이용한 방법이다. 이 외에도 다른 방법들이 있다.
- ↑ 11의 배수는 다른 방법으로, 만약 홀수번째 자리(일의 자리, 백의 자리, 만의 자리... 등)와 짝수번째 자리(십의 자리, 천의 자리, 십만의 자리... 등)의 각각의 합의 차가 0 또는 11의 배수이면 그 수는 11의 배수이다. (예: 11110 → 1+1+0=2, 1+1=2, 2-2=0 → 11의 배수.)