로그인하고 있지 않습니다. 편집하면 당신의 IP 주소가 공개적으로 기록됩니다. 계정을 만들고 로그인하면 편집 시 사용자 이름만 보이며, 위키 이용에 여러 가지 편의가 주어집니다.스팸 방지 검사입니다. 이것을 입력하지 마세요! 素因數分解. Prime Factorization. ==개요== 자연수의 소인수분해(factorization)란 [[합성수]]를 [[소수]]인 인수(약수)들의 곱으로 나타내는 것이다. <ref>합성수가 아니어도 상관은 없지만 그러면 소인수분해를 하는 의미가 없어진다.</ref>예를 들면 6=2×3과 같이. [[소수]]를 처음 배우는 초등학교부터 자주는 아니더라도 계속 쓰이는 기본적인 수학 도구. 다만, 소인수분해가 '''왜''' 되는지 아는 사람은 [[수학과]]를 제외하고 드물다. 모든 [[합성수]]가 당연히 소인수분해가 된다고 흔히들 생각하는데, 큰 오산이다. 수학에 [[공리]]를 제외하고 당연한 것은 없으며, 모두 수학적인 증명을 요구한다. 이에 대해서는 아래 산술의 기본 정리 부분을 참고하자. 이 소인수분해와 비슷한 개념으로 (다항식의) 인수분해가 있다. 그런데 [[환 (수학)|환]]에서는 다항식의 인수분해와 구별할 필요가 없기 때문에 둘 다 인수분해라 한다. 어떤 원소를 (소수가 아니라) 기약원(irreducible element)들의 곱으로 나타내는 것을 인수분해라 한다. == 산술의 기본 정리 == Fundamental Theorem of Arithmetic {{인용문|1보다 큰 모든 정수 <math>n</math>은 <math>n={p_1}^{e_1}{p_2}^{e_2}\cdots{p_n}^{e_n}</math>로 (순서가 바뀐 것을 제외하고) '''유일하게''' 나타낼 수 있다. 단, 여기서 <math>e_i\geq0</math>이고, <math>p_i</math>는 서로 다른 소수이다.}} 우리가 소인수분해를 당연하게 여길 수 있게 만들어 주는 정리. 이름이 비슷한 [[대수학의 기본 정리]]는 듣기만 해도 정신이 날아갈 듯한 증명을 사용하지만, 이 산술의 기본정리는 {{--|좀 아주 많이 똑똑한}} 초등학생도 증명을 할 수 있다. 증명은 [[존재성과 유일성|'''존재성'''과 '''유일성''']], 두 파트로 나뉜다. === 존재성 === 1보다 큰 임의의 양의 정수 <math>n</math>의 두번째로 작은 약수는 [[소수]]여야 한다.<ref>제일 작은 약수는 당연히 1이다.</ref> 만약 <math>m</math>이 <math>n</math>의 두번째로 작은 약수인데 [[합성수]]라면, 합성수의 정의에 의해 <math>l\mid m,\,1< l< m</math>인 소수 <math>l</math>이 존재한다. 그런데 <math>m\mid n</math>이므로 <math>l\mid n</math>이고, 이는 <math>m</math>이 두번째로 작은 약수라는 정의에 모순된다. 따라서 <math>m</math>은 소수이다. 따라서, <math>n=p_1n_1</math>로 표현할 수 있고 (<math>p_1=m</math>), <math>n_1</math>이 소수라면 증명은 끝. 소수가 아니라면 위 과정을 계속 반복하여 <math>n</math>을 소수의 곱으로만 표현할 수 있다. 즉, 1보다 큰 임의의 양의 정수 <math>n</math>의 소인수분해가 '''존재'''한다. === 유일성 === * 증명 1 [[귀류법]]을 사용해 증명한다. 집합 <math>A</math>를 <math>A=\left\{x\in\mathbb{N}|x> 1, x\right.</math>의 소인수분해는 유일하지 않음<math>\left.\right\}</math>로 정의하자. [[자연수]]의 정렬성에 의해 집합 <math>A</math>에는 가장 작은 원소가 존재한다.<ref>정확히는 <math>A</math>가 공집합이 아니어야 존재한다. 헌데 <math>A</math>가 공집합이면 1보다 큰 모든 정수의 소인수분해가 유일함을 의미하게 된다.</ref> 이를 <math>n</math>라 하자. 그럼, <math>p_1\leq p_2\leq\cdots\leq p_k,\,q_1\leq q_2\leq\cdots\leq q_l</math>을 만족하는 소수 <math>p_1,p_2,\cdots,p_k,q_1,q_2,\cdots,q_l</math>에 대해 <math>n=p_1p_2\cdots p_k=q_1q_2\cdots q_l</math>이 성립한다. 여기서 만약 어떤 <math>i,j</math>에 대해 <math>p_i=q_j</math>이면, <math>n/p_i</math>도 소인수분해가 유일하지 않고, <math>n> n/p_i</math>이므로 <math>n</math>이 <math>A</math>의 가장 작은 원소라는 사실에 모순된다. 즉, <math>p_i\neq q_j</math>. 한편, <math>{p_1}^2\leq n, {q_1}^2\leq n</math>이고 <math>{p_1}^2</math>와 <math>{q_1}^2</math>은 동시에 <math>n</math>이 될 수 없으므로,<ref>만약 둘이 동시에 <math>n</math>이면 <math>p_1=q_1</math>이고, 이는 위의 <math>p_i\neq q_j</math>에 모순된다.</ref> <math>0< p_1q_1< n</math>이다. 이제 <math>N=n-p_1q_1</math>이라 정의하자. <math>0< N< n</math>이고 <math>p_1\mid N,\,q_1\mid N</math>이므로, <math>1< N< n</math>이 성립하고, <math>N</math>은 유일한 소인수분해를 가진다.<ref>유일하지 않으면 <math>N\in A</math>이고, 이는 <math>n</math>이 <math>A</math>의 가장 작은 원소라는 사실에 모순이다.</ref> 또한 <math>N</math>의 유일한 소인수분해에는 <math>p_1</math>과 <math>q_1</math>이 둘 다 들어간다. 따라서 적당한 양의 정수 <math>M</math>에 대해 <math>N=p_1q_1M</math>. 이제 <math>n=N+p_1q_1=p_1q_1\left(M+1\right)</math>이고, 양변을 <math>p_1</math>로 나누면 <math>n/p_1=q_1\left(M+1\right)</math>. 곧, <math>p_2p_3\cdots p_k=q_1\left(M+1\right)</math>이다. 여기서 <math>q_1\neq p_i</math>이므로 <math>n/p_1</math>는 유일하지 않은 소인수분해를 가진다.<ref><math>M+1</math>이 어떻게 소인수분해 되는가와는 상관없다.</ref> 또한 <math>1< n/p_1</math>이므로 <math>n/p_1\in A</math>이고, <math>n/p_1< n</math>이므로 이는 <math>n</math>이 집합 <math>A</math>의 가장 작은 원소라는 사실에 모순된다. 따라서 1보다 큰 임의의 양의 정수의 소인수분해는 '''유일'''하다. {{--|이게 어딜 봐서 초등학생도 할 수 있냐}} * 증명 2 <math>n = p_1 \cdots p_k = q_1 \cdots q_l</math>이 1보다 큰 양의 정수 <math>n</math>의 두 가지 소인수분해라고 하자(단, <math>k,\; l</math>은 자연수이고 <math>k \leq l</math>). <math>p_i</math>들 그리고 <math>q_j</math>이 서로 같은지 다른지는 이 증명에서 아무 문제가 안 되기 때문에 거듭제곱 표현을 전부 풀어 적었고, 이렇게 적어도 소인수분해라는 데 이의는 없을 것이다. 이제 <math>p_1 | q_1 \cdots q_l</math>이고 <math>p_1</math>은 [[소수]]이므로 소수의 정의에 의해 <math>q_1,\; \cdots,\; q_l</math> 중 <math>p_1</math>로 나누어 떨어지는 것이 있을 것이다. 이를 일반성을 잃지 않고 <math>q_1</math>이라 하자. 이제 <math>q_1</math>도 소수이므로 역시 소수의 정의에 의해 <math>q_1</math>의 양의 약수는 <math>1,\; q_1</math> 둘뿐이다. 따라서 <math>p_1=q_1</math>일 수밖에 없다. 따라서 양변에서 <math>p_1=q_1</math>을 소거하여 <math>p_2 \cdots p_k = q_2 \cdots q_l</math>을 얻는다. 이제 <math>p_2,\; \cdots,\; p_k</math>에 대해 위 과정을 반복하여 최종적으로 <math>1 = q_{k+1} \cdots q_l</math>을 얻는다. 그런데 좌변은 약수가 1뿐이므로 위 식의 우변에는 소수가 하나라도 있으면 안 되고, 따라서 <math>k=l</math>을 얻는다. 나아가 위 반복하는 과정에서 <math>p_1=q_1,\; \cdots,\; p_k=q_k</math>인 점까지 알 수 있다. 따라서 위 두 개의 소인수분해는 서로 같고, 따라서 소인수분해가 유일함을 알 수 있다. == 소인수분해를 하는 방법 == 이 문단에서는 1보다 큰 어떤 정수 <math>N</math>이 주어졌을 때, [[약수]]를 찾는 여러 가지 기술에 대해 소개한다. 먼저 가장 쉬운 방법은 아래의 배수 판정법을 이용하는 것이다. 정수 <math>N</math>에 대해서, * 2의 배수: 끝자리가 짝수. * 3의 배수: 각 자릿수의 합이 3의 배수. * 4의 배수: 맨 뒤 두자리가 4의 배수. * 5의 배수: 끝자리가 0이나 5. * 6의 배수: <math>N</math>이 2의 배수이면서 3의 배수. * 8의 배수: 맨 뒤 세자리가 8의 배수. * 9의 배수: 각 자릿수의 합이 9의 배수. * 10의 배수: 끝자리가 0. * 7, 11, 13의 배수: 일의 자리부터 세 자리씩 끊은 뒤, 각 부분을 교대로 빼고 더한 값이 7, 11, 13의 배수.<ref>123456789를 예시로 들면, 123-456+789=456이 7의 배수가 아니므로 원래 수는 7의 배수가 아니다. 59255924를 예시로 들면, 59-255+924=728이 7의 배수이므로 원래 수는 7의 배수이다.</ref><ref>이 방법은 1001=7*11*13 임을 이용한 방법이다. 이 외에도 다른 방법들이 있다.</ref> 아래 정리를 사용할 수도 있다. {{인용문|모든 [[합성수]]는 그 수의 [[제곱근]]보다 작거나 같은 약수를 같는다.}} 증명은 아래와 같다. {{인용문2|<math>n</math>을 합성수라 하자. 그러면 <math>n=ab,\,1< a,b< n</math>이다. 만약 <math>a,b</math>가 둘 다 <math>\sqrt n</math>보다 크다면, <math>n=\sqrt n\sqrt n< ab=n</math>이 되어 모순이다. 따라서 <math>a,b</math>중 적어도 하나는 <math>\sqrt n</math>보다 작다.|}} 이 정리에 의해 어떤 큰 수를 소인수분해 할 때, 그 수의 제곱근 보다 큰 수로 나눌 필요는 없다는 사실을 알 수 있다. 이는 [[노가다]]를 통해 소인수분해를 하는 시간을 크게 단축시켜 준다. == 관련 항목 == * [[소수]] * [[합성수]] * [[인수분해]] * [[대수학의 기본 정리]] {{각주}} {{수}} [[분류:정수론]] 요약: 리브레 위키에서의 모든 기여는 크리에이티브 커먼즈 저작자표시-동일조건변경허락 3.0 라이선스로 배포됩니다(자세한 내용에 대해서는 리브레 위키:저작권 문서를 읽어주세요). 만약 여기에 동의하지 않는다면 문서를 저장하지 말아 주세요. 글이 직접 작성되었거나 호환되는 라이선스인지 확인해주세요. 리그베다 위키, 나무위키, 오리위키, 구스위키, 디시위키 및 CCL 미적용 사이트 등에서 글을 가져오실 때는 본인이 문서의 유일한 기여자여야 하고, 만약 본인이 문서의 유일한 기여자라는 증거가 없다면 그 문서는 불시에 삭제될 수 있습니다. 취소 편집 도움말 (새 창에서 열림) | () [] [[]] {{}} {{{}}} · <!-- --> · [[분류:]] · [[파일:]] · [[미디어:]] · #넘겨주기 [[]] · {{ㅊ|}} · <onlyinclude></onlyinclude> · <includeonly></includeonly> · <noinclude></noinclude> · <br /> · <ref></ref> · {{각주}} · {|class="wikitable" · |- · rowspan=""| · colspan=""| · |} {{lang|}} · {{llang||}} · {{인용문|}} · {{인용문2|}} · {{유튜브|}} · {{다음팟|}} · {{니코|}} · {{토막글}} {{삭제|}} · {{특정판삭제|}}(이유를 적지 않을 경우 기각될 가능성이 높습니다. 반드시 이유를 적어주세요.) {{#expr:}} · {{#if:}} · {{#ifeq:}} · {{#iferror:}} · {{#ifexist:}} · {{#switch:}} · {{#time:}} · {{#timel:}} · {{#titleparts:}} __NOTOC__ · __FORCETOC__ · __TOC__ · {{PAGENAME}} · {{SITENAME}} · {{localurl:}} · {{fullurl:}} · {{ns:}} –(대시) ‘’(작은따옴표) “”(큰따옴표) ·(가운뎃점) …(말줄임표) ‽(물음느낌표) 〈〉(홑화살괄호) 《》(겹화살괄호) ± − × ÷ ≈ ≠ ∓ ≤ ≥ ∞ ¬ ¹ ² ³ ⁿ ¼ ½ ¾ § € £ ₩ ¥ ¢ † ‡ • ← → ↔ ‰ °C µ(마이크로) Å °(도) ′(분) ″(초) Α α Β β Γ γ Δ δ Ε ε Ζ ζ Η η Θ θ Ι ι Κ κ Λ λ Μ μ(뮤) Ν ν Ξ ξ Ο ο Π π Ρ ρ Σ σ ς Τ τ Υ υ Φ φ Χ χ Ψ ψ Ω ω · Ά ά Έ έ Ή ή Ί ί Ό ό Ύ ύ Ώ ώ · Ϊ ϊ Ϋ ϋ · ΐ ΰ Æ æ Đ(D with stroke) đ Ð(eth) ð ı Ł ł Ø ø Œ œ ß Þ þ · Á á Ć ć É é Í í Ĺ ĺ Ḿ ḿ Ń ń Ó ó Ŕ ŕ Ś ś Ú ú Ý ý Ź ź · À à È è Ì ì Ǹ ǹ Ò ò Ù ù · İ Ż ż ·  â Ĉ ĉ Ê ê Ĝ ĝ Ĥ ĥ Î î Ĵ ĵ Ô ô Ŝ ŝ Û û · Ä ä Ë ë Ï ï Ö ö Ü ü Ÿ ÿ · ǘ ǜ ǚ ǖ · caron/háček: Ǎ ǎ Č č Ď ď Ě ě Ǐ ǐ Ľ ľ Ň ň Ǒ ǒ Ř ř Š š Ť ť Ǔ ǔ Ž ž · breve: Ă ă Ğ ğ Ŏ ŏ Ŭ ŭ · Ā ā Ē ē Ī ī Ō ō Ū ū · à ã Ñ ñ Õ õ · Å å Ů ů · Ą ą Ę ę · Ç ç Ş ş Ţ ţ · Ő ő Ű ű · Ș ș Ț ț 이 문서에서 사용한 틀: 틀:-- (원본 보기) (준보호됨)틀:Skin (원본 보기) (준보호됨)틀:각주 (원본 보기) (준보호됨)틀:둘러보기 상자 (원본 보기) (보호됨)틀:둘러보기 상자/핵심 (원본 보기) (보호됨)틀:수 (편집) 틀:인용문 (원본 보기) (준보호됨)틀:인용문2 (원본 보기) (준보호됨)틀:취소선 (원본 보기) (준보호됨)틀:틀바 (원본 보기) (준보호됨)