소인수분해 결과 이해하기
아래 표는 익숙한 몇 가지 수의 소인수분해를 보여 주어 지수 표기가 어떻게 작동하는지 설명합니다.
| 수 | 소인수분해 | 약수의 개수 |
|---|---|---|
| 12 | 2² × 3 | 6 |
| 100 | 2² × 5² | 9 |
| 360 | 2³ × 3² × 5 | 24 |
| 17 (소수) | 17 (자기 자신, 지수 1) | 2 |
| 1024 | 2¹⁰ | 11 |
- 소수의 소인수분해는 지수가 1인 자기 자신이며, 약수는 언제나 1과 자기 자신 두 개뿐입니다. 이것이 바로 소수를 정의하는 성질입니다.
- 1은 소수도 합성수도 아니며 소인수분해를 가지지 않습니다(공곱입니다). 이 계산기는 2 이상의 입력을 요구합니다.
- 매우 큰 수의 경우 시행 나눗셈은 그 수의 제곱근까지 후보 소수를 시험해야 하므로 계산이 느려집니다. 이 때문에 (수백 자리에 이르는) 극도로 큰 수의 인수분해는 계산상 어려우며, 이는 RSA 암호의 보안 근거가 됩니다.
소인수분해란 무엇입니까?
소인수분해는 정수를 곱하여 그 수를 만들어 내는 소수들의 집합으로 나누어 나타내는 과정입니다. 소수는 1보다 큰 정수 중에서 양의 약수가 1과 자기 자신 두 개뿐인 수입니다(2, 3, 5, 7, 11, 13, ... 이 처음 몇 개의 소수입니다). 예를 들어 360은 2³ × 3² × 5로 분해되며, 이는 360 = 2×2×2×3×3×5임을 뜻합니다.
정수론의 기초를 이루는 결과 중 하나인 산술의 기본 정리는 1보다 큰 모든 정수가 인수를 쓰는 순서를 제외하면 단 하나의 소인수분해만을 가진다는 것을 보장합니다. 이 유일성 덕분에 소인수분해는 여러 개의 똑같이 타당한 답이 존재하는 작업이 아니라 명확하게 정의된 신뢰할 수 있는 연산이 됩니다.
소인수분해는 수학과 컴퓨터 과학의 핵심 영역을 뒷받침합니다. 두 수의 최대공약수와 최소공배수를 구하고, 한 수의 모든 약수를 결정하며, 분수와 근호를 간단히 하는 데 쓰입니다. 또한 매우 큰 수에 대해서는 그 계산상의 어려움이 RSA 공개키 암호의 수학적 토대가 되는데, 이는 큰 수를 인수분해하는 것이 그 인수들을 곱하는 것보다 훨씬 어렵다는 사실에 의존합니다.
이 소인수분해 계산기 사용 방법
- 2 이상의 정수를 입력합니다(최대 1조).
- 계산기는 표준적인 시행 나눗셈 방법에 따라 1만 남을 때까지 가능한 가장 작은 소인수로 반복해서 나눕니다.
- 소인수분해 결과를 지수 형태(예: 2³ × 3² × 5)로 확인합니다. 각 지수는 해당 소수가 곱에 몇 번 나타나는지를 보여 줍니다.
- 그 수가 가지는 양의 약수의 총 개수와 그 약수들의 합을 확인합니다. 둘 다 소인수분해에서 직접 도출됩니다.
소인수분해, 약수의 개수, 약수의 합을 구하는 방법
시행 나눗셈은 2부터 시작해 연속된 후보 소수를 시험하면서 그 소수로 나누어떨어지는 횟수만큼 나눈 뒤 다음 후보로 넘어가는 방식으로 소인수분해를 구합니다. 계산 예시: 360 ÷ 2 = 180, ÷2 = 90, ÷2 = 45(더 이상 2로 나누어떨어지지 않으므로 2는 3번 나타납니다). 45 ÷ 3 = 15, ÷3 = 5(더 이상 3으로 나누어떨어지지 않으므로 3은 2번 나타납니다). 5 ÷ 5 = 1(5는 1번 나타납니다). 결과: 360 = 2³ × 3² × 5.
소인수분해 n = p₁^e₁ × p₂^e₂ × ... × pₖ^eₖ 를 알고 나면, 양의 약수의 총 개수(1과 n 자신 포함)는 각 지수에 1을 더한 뒤 그 결과들을 곱하여 구합니다: (e₁+1) × (e₂+1) × ... × (eₖ+1). 360 = 2³ × 3² × 5¹ 의 계산 예시: (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24개의 약수.
모든 약수의 합은 곱셈적 약수합 공식으로 구합니다. 소인수분해에 나오는 각 소수 거듭제곱 p^e 의 기여분은 (p^(e+1) − 1) ÷ (p − 1), 즉 등비급수 1 + p + p² + ... + p^e 의 합이며, 이 기여분들을 모든 소인수에 걸쳐 곱합니다. 360의 계산 예시: 2³ 항은 (2⁴−1)/(2−1) = 15를 기여하고, 3² 항은 (3³−1)/(3−1) = 13을 기여하며, 5¹ 항은 (5²−1)/(5−1) = 6을 기여합니다. 15 × 13 × 6 = 1,170으로, 이것이 360의 24개 약수 전체의 합입니다.
흔한 실수
- 1에 도달하기 전에 분해를 일찍 멈추는 것 — 찾아낸 각 인수는 다음 후보 소수로 넘어가기 전에 (한 번만이 아니라) 완전히 나누어 없애야 합니다.
- 1을 소수로 취급하는 것 — 현대 수학의 관례상 1은 소수도 합성수도 아니며, 이를 인수분해에 포함하면 산술의 기본 정리가 보장하는 유일성이 깨집니다.
- 약수를 셀 때 밑이 되는 소수뿐 아니라 지수도 중요하다는 점을 잊는 것 — 약수의 개수 공식은 서로 다른 소수의 개수가 아니라 각 소수에 대해 (지수 + 1)을 사용합니다.
- 모든 큰 수에 작은 소인수가 있다고 가정하는 것 — 많은 큰 수, 특히 두 개의 큰 소수의 곱은 작은 인수를 전혀 가지지 않으며, 바로 이 성질이 암호학적 응용에 유용하게 쓰입니다.
자주 묻는 질문
수의 소인수분해는 어떻게 구합니까?
그 수를 나누어떨어지게 하는 가장 작은 소수로 반복해서 나누되 더 이상 나누어떨어지지 않을 때까지 같은 소수로 계속 나눈 뒤, 다음 소수로 넘어가 남은 몫이 1이 될 때까지 반복합니다. 360의 경우: 2로 세 번 나누고(360→180→90→45), 3으로 두 번 나눈 뒤(45→15→5), 5로 한 번 나누면(5→1) 360 = 2³ × 3² × 5 가 됩니다.
어떤 수의 약수는 몇 개입니까?
소인수분해의 각 지수에 1을 더한 뒤 그 결과들을 모두 곱합니다. 360 = 2³ × 3² × 5¹ 의 경우 약수의 개수는 (3+1) × (2+1) × (1+1) = 4 × 3 × 2 = 24개입니다. 여기에는 1과 그 수 자신을 포함한 모든 양의 약수가 계산됩니다.
산술의 기본 정리란 무엇입니까?
산술의 기본 정리는 1보다 큰 모든 정수가 소수들을 나열하는 순서를 제외하면 정확히 한 가지 방법으로 소수들의 곱으로 표현될 수 있다는 정리입니다. 이 유일성 덕분에 소인수분해는 여러 개의 똑같이 타당한 답이 있는 작업이 아니라 명확히 정의된 연산이 되며, 정수론의 상당 부분이 여기에 기반합니다.
1은 소수입니까?
아닙니다. 현대 수학의 관례상 1은 소수도 합성수도 아닙니다. 소수는 서로 다른 양의 약수가 정확히 두 개(1과 자기 자신)인 수로 정의되는데, 1은 양의 약수가 하나(자기 자신)뿐이므로 정의를 만족하지 않습니다. 또한 1을 소수에서 제외하는 것은 산술의 기본 정리가 성립하기 위해서도 필요합니다. 그렇지 않으면 어떤 수든 1이라는 인수를 얼마든지 덧붙여 '분해'할 수 있기 때문입니다.
소인수분해는 왜 암호에 중요합니까?
현대의 RSA 공개키 암호는 두 개의 큰 소수를 곱하는 것은 계산상 쉽지만, 그 큰 곱을 원래의 소수들로 되돌려 인수분해하는 것은 현재 알려진 고전 알고리즘으로는 계산상 매우 어렵다는 사실에 의존합니다. 곱하기는 쉽고 인수분해는 어렵다는 이 비대칭성 덕분에 공개키(곱)는 공개적으로 공유하면서도 개인키(소인수)는 비밀로 유지되며, 충분히 큰 소수를 쓰면 현실적인 시간 안에서는 사실상 복원할 수 없습니다.
어떤 수의 모든 약수의 합은 어떻게 구합니까?
소인수분해 n = p₁^e₁ × p₂^e₂ × ... 를 이용해 각 소인수에 대해 (pᵢ^(eᵢ+1) − 1) ÷ (pᵢ − 1)을 계산한 뒤 그 결과들을 곱합니다. 360 = 2³ × 3² × 5 의 경우 2³ 항은 (2⁴−1)/(2−1)=15, 3² 항은 (3³−1)/(3−1)=13, 5¹ 항은 (5²−1)/(5−1)=6을 주며, 15×13×6 = 1,170이 360의 모든 약수의 합입니다.
참고 자료
- Rosen KH. Elementary Number Theory and Its Applications. 6th ed. Pearson, 2010. (Fundamental theorem of arithmetic, divisor functions.)
- Hardy GH, Wright EM. An Introduction to the Theory of Numbers. 6th ed. Oxford University Press, 2008.
- Rivest RL, Shamir A, Adleman L. A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. Communications of the ACM, 1978; 21(2): 120–126. (RSA and the factoring problem.)