소인수분해 계산기

소인수 분해란 무엇인가?

소인수 분해는 복합 수를 유일한 소수 기본 블록으로 분해하는 과정이다. 소수는 1보다 큰 자연수이며, 1과 자기 자신으로만 나누어지는 수이다. 예를 들어, 2, 3, 5, 7, 11, 13, 17, 19, 23. 복합 수는 1보다 큰 정수이며, 소수가 아닌 수이다. 즉, 1과 자기 자신 이외의 다른 인수를 가진다.

360과 같은 수를 소인수 분해하면, 소수로 표현할 수 있다: 360 = 2³ × 3² × 5. 이 표현은 각 정수마다 유일하다. 이는 수의 기본 정리에 의해 보장된다. 이 정리는 모든 정수는 1보다 크면 소수이거나, 소수로만 구성된 유일한 곱으로 표현할 수 있다는 것을 말한다. (인수들의 순서를 무시한다)

이 개념은 2,000년 이상 연구되어 왔다. 유clid의 Elements (기원전 300년경)에는 소수의 무한성의 증명과 기본 정리의 초기 형태가 포함되어 있다. 따라서 소인수 분해는 수학의 가장 오래된 지속적으로 연구되는 문제 중 하나이다.

수의 기본 정리

수의 기본 정리는 수론의 기초이다. 두 가지 부분으로 구성된다. 첫 번째, 1보다 큰 모든 정수는 소수로 표현할 수 있다. 두 번째, 이 표현은 유일하다 (인수들의 순서를 무시한다). 예를 들어, 12 = 2² × 3, 어떤 방법으로든 소인수 분해를 하더라도, 항상 2와 3의 소인수와 같은 지수만을 얻을 수 있다.

이 유일성은 소인수 분해의 힘을 만든다. 없으면, GCD와 LCM를 찾는 것, 분수 간소화, 또는 약수 속성을 증명하는 것과 같은 산술 연산이 훨씬 복잡해질 것이다. 이 정리는 초등 수론과 중간 수론의 거의 모든 것을 뒷받침한다.

흥미로운 결과: 정수 n가 정수 m을 나누는지 알고 싶다면, 그들의 소인수 분해를 비교하면 된다. n은 m을 나누는 경우, n의 인수 중 소수 p가 m의 인수 중 p의 지수가 n의 지수보다 같거나 더 높을 때이다.

소인수 찾기: 단계별 방법

소인수 분해를 위한 두 가지 주요 수동 방법이 있다: 인수 나무와 반복적인 나누기.

인수 나무 방법: 수를 위로 쓰고, 그 수를 두 개의 인수로 나누어 분기한다. 각 복합 인수를 나누어 분기할 때까지 계속한다. 180의 경우: 4와 45로 분기 → 4를 2와 2로 분기 → 45를 9와 5로 분기 → 9를 3과 3으로 분기. 모든 잎 노드 수집: 2 × 2 × 3 × 3 × 5 = 2² × 3² × 5.

반복적인 나누기 방법: 수를 가장 작은 소수로 나누어, 나누어 떨어지면, 그 몫을 다시 가장 작은 소수로 나누어, 그 몫을 다시 가장 작은 소수로 나누어, ... 반복한다. 360의 경우: 360 ÷ 2 = 180 → 180 ÷ 2 = 90 → 90 ÷ 2 = 45 → 45 ÷ 3 = 15 → 15 ÷ 3 = 5 → 5는 소수이다. 결과: 2³ × 3² × 5.

중요한 단축: 소인수까지의 제곱근까지만 테스트하면 된다. 만약 제곱근 n이 n을 나누지 못한다면, n은 소수이다. 예를 들어, n = 97의 경우, √97 ≈ 9.85이므로, 2, 3, 5, 7까지만 테스트하면 된다. 그 중 하나도 97을 나누지 못하므로, 97은 소수이다. 큰 수의 경우 작업량이 훨씬 줄어든다.

소인수분해 참조 표

아래는 일반적인 정수의 소인수분해를 보여주는 참조 표입니다.

인수 개수 공식: 만약 n = p₁^a × p₂^b × p₃^c… 이라면, 총 인수 개수는 (a+1)(b+1)(c+1)… 이다. 360 = 2³ × 3² × 5¹ 인 경우, 인수 개수는 (3+1)(2+1)(1+1) = 4 × 3 × 2 = 24 이다.

소인수분해의 응용

최대 공배수 (GCD): GCD(48, 180) 을 찾으려면, 48 = 2⁴ × 3, 180 = 2² × 3² × 5 이라고 분해한 후, 공통의 소인수에 대한 최소 지수를 취한다: GCD = 2² × 3 = 12. GCD 는 분수를 단순화하는 데 사용된다: 48/180 = 4/15 (12으로 모두 나누기).

최소 공배수 (LCM): 두 분해의 각 소인수에 대한 최대 지수를 취한다. LCM(48, 180) = 2⁴ × 3² × 5 = 720. LCM 는 분자와 분모가 다른 분수의 합을 계산할 때 사용된다 — 공통의 분모가 필요하며, 이는 LCM(denominator₁, denominator₂) 이다.

암호화 (RSA): 큰 수의 분해의 어려움 — 특히 두 큰 소수의 곱 — RSA 암호화의 수학적 기초이다. RSA-2048은 1024비트 소수의 곱으로 구성된 공개 키를 사용한다. 분해하는 데는 현재 알고리즘으로는 우주가 태어난 지보다 더 오래 걸린다. 이 보안은 HTTPS, 이메일 암호화 및 디지털 서명에 기반을 두고 있다.

식의 단순화: 대수학에서 다항식 분해는 정수 분해와 개념적으로 유사하다. 12 = 4 × 3 = 2² × 3 인 것처럼, 표현 x² − 9는 (x−3)(x+3)로 분해된다. 소인수 분해의 사고방식은 직접 대수학적 조작에 전이된다.

소수와 그 분포

소수 자체가 무한히 매력적이다. 첫 번째 소수는 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47 ... 숫자가 커질수록 소수는 더 드물지만 멈추지 않는다. 유clid는 2,300년 전의 단순한 반대 증명으로 이를 증명했다.

소수 이론 (Prime Number Theorem) (1896년 하담과 드 라 발레 푸신이 독립적으로 증명했다) 는 n 이하의 소수의 개수가 n / ln(n) 인 것과 같이 근사한다. 이는 n 근처에 1/ln(n) 개의 숫자 중 1개가 소수라는 것을 의미한다 — 1백만 근처에는 1/14 개의 숫자가 소수이고, 1억 근처에는 1/21 개의 숫자가 소수이다.

소수에 대한 특수한 범주는 다음과 같다: 쌍소수 (twin primes) (2 차이로 쌍을 이룬다: 11 & 13, 17 & 19), 메르센 소수 (Mersenne primes) (2^p − 1 형태; 2024년 현재 가장 큰 소수는 41,000,000 자리 이상의 메르센 소수이다), 소피 제르맹 소수 (Sophie Germain primes) (p 에서 2p+1 도 소수인 p). 쌍소수에 대한 무한 존재 여부는 여전히 개방 문제 — 쌍소수 추측.

인수분해 알고리즘: 시도 분할에서 고급 방법까지

작은 수 (1억 미만) 에서, 시도 분할은 빠르고 직관적: 2로 나누고, 모든 홀수 (n의 제곱근)까지 시도한다. 우리의 계산기는 이 접근법을 사용하고 10억 이상의 수를 밀리초에 처리한다.

큰 수에 대해, 수학자들은 더 정교한 알고리즘을 개발했다. 페르마의 인수 분해 방법은 n을 두 제곱의 차로 표현: n = a² − b² = (a+b)(a−b). 폴라드의 rho 알고리즘 (1975)은 작은 인수에 대한 확률적 방법으로, n^(1/4) 시간에 실행되고 실제 세계의 많은 응용 프로그램에서 사용된다.

가장 강력한 알려진 일반적인 목적 인수 분해 알고리즘은 일반 수장 필드 분해 (GNFS)이며, 이 알고리즘은 지수 시간에 실행된다. GNFS는 2009 년에 768 비트 RSA 도전 수 (RSA-768)를 분해하기 위해 사용되었으며, 단일 코어 CPU 시간의 2,000 년에 해당하는 수많은 컴퓨터를 통해 분산되었다. RSA-2048는 클래식 컴퓨터로 인수 분해가 계산적으로 불가능하다.

양자 컴퓨터는 이론적으로 클래식 컴퓨터보다 효율적으로 큰 수를 분해할 수 있는 쇼르의 알고리즘 (1994)을 사용할 수 있다. 이것은 양자 공격에 저항하는 암호화 개발 — 양자 공격에 저항하는 암호화 — 오늘날 주요 연구 분야이다.

교육 및 경쟁 수학에서 인수 분해

인수 분해는 중학교와 고등학교 수학의 핵심 기술이다. 분수 간단화, GCD 및 LCM 찾기, 완전 제곱수 및 완전 세제곱수 작업, 분할 가능성 규칙 이해를 가능하게 한다. 인수 분해를 마스터하면, 표현 대신 정수에 대한 인수 분해와 유사한 기술을 적용하여 대수학에서 인수 분해를 이해하는 데 도움이 된다.

경쟁 수학 (AMC, AIME, 올림픽)에서 인수 분해 문제가 자주 등장한다. 예를 들어, "1,000,000의 양의 정수 인수는 몇 개인가?" 1,000,000 = 10^6 = (2 × 5)^6 = 2^6 × 5^6이므로, 답은 (6+1)(6+1) = 49이다. 이러한 유형의 문제는 학생들에게 곱셈적으로 생각하는 것이 보상된다.

인수 분해에서 지수도 개념을 이해하면, 완전 제곱수 (모든 지수는 짝수), 완전 세제곱수 (모든 지수는 3으로 나누어 떨어짐), 주어진 수의 가장 작은 완전 제곱수 — 모든 시험 주제이다.

분해법을 사용하여 분수와 근의 단순화

분해법은 분수의 단순화에 가장 체계적인 방법입니다. 84/126을 단순화하려면, 84 = 2² × 3 × 7과 126 = 2 × 3² × 7을 분해합니다. GCD = 2 × 3 × 7 = 42. 따라서 84/126 = (84÷42)/(126÷42) = 2/3. 추측이 필요하지 않습니다. - 분해법은 GCD를 직접 노출합니다.

근의 단순화에도 분해법은 강력합니다. √180을 단순화하려면, 180 = 2² × 3² × 5를 분해합니다. 2² × 3² × 5의 제곱근은 2 × 3 × √5 = 6√5입니다. 3의 제곱근은 ∛(108) = ∛(2² × 3³) = 3∛4입니다. 3의 제곱근에서 3의 그룹이 나옵니다.

경쟁 수학에서 이러한 기술은 자주 나타납니다. 일반적인 문제 유형: "360n은 완전 제곱수인 가장 작은 정수 n을 찾으십시오." 360 = 2³ × 3² × 5이므로, 모든 지수는 짝수여야 합니다. 현재 2의 지수는 3 (홀수)이고 5의 지수는 1 (홀수)입니다. 따라서 n은 적어도 2¹ × 5¹ = 10을 제공해야 합니다. 답: n = 10. 확인: 360 × 10 = 3600 = 60². ✓

약수 개수, 완전 수, 약수의 합

분해법은 약수의 완전한 분석을 열어줍니다. n = p₁^a × p₂^b × p₃^c라고 할 때, 약수의 개수는 τ(n) = (a+1)(b+1)(c+1)입니다. 약수의 합은 σ(n) = ((p₁^(a+1)−1)/(p₁−1)) × ((p₂^(b+1)−1)/(p₂−1)) × ...

12 = 2² × 3의 경우, τ(12) = (2+1)(1+1) = 6 (약수: 1,2,3,4,6,12). σ(12) = ((2³−1)/(2−1)) × ((3²−1)/(3−1)) = 7 × 4 = 28. 완전 수는 자신의 적절한 약수의 합과 같습니다 (자신을 제외한 약수). σ(n) − n = n → σ(n) = 2n. 6 = 2 × 3의 경우, σ(6) = 12 = 2×6. ✓ 6은 완전수입니다! 28 = 2² × 7의 경우, σ(28) = 56 = 2×28. ✓ 28은 완전수입니다!

2024년까지 51개의 완전수만 알려져 있으며, 모두 짝수이며, 모두 2^(p−1)(2^p−1) 형태입니다. 2^p−1이 메르센 소수인 경우. 어떤 홀수 완전수가 존재하는지 여부는 수학의 가장 오래된 개방 문제 중 하나입니다. - 홀수 완전수는 발견되지 않았지만, 불가능하다고 증명되지 않았습니다.

빠른 참조: 약수 가능성 규칙

분해를 수행하기 전에 약수 가능성 규칙은 빠른 약수 확인을 위해 사용합니다. 이 정신적 단축은 수동적 분해와 시험 환경에서 효율적인 분해를 위한 필수입니다.

이러한 규칙을 기억하면 분해가 훨씬 빠르게 됩니다. 2,520의 경우, 짝수 (2로 나누어집니다), 자릿수 합=9 (3으로 나누어집니다), 마지막 자릿수가 0 (5로 나누어집니다). 2로 시작: 2520÷2=1260÷2=630÷2=315÷3=105÷3=35÷5=7. 따라서 2520 = 2³ × 3² × 5 × 7 — 매우 완전한 수에 48개의 약수가 있습니다.