[정수론 입문 시리즈 9편] 소인수분해는 정수의 구조를 어떻게 드러낼까?

프로그램이 임의의 큰 숫자를 입력받았다고 해 봅시다. 그 숫자를 이루는 “소수 부품”은 매번 같은 방식으로 정해질까요, 아니면 분해하는 순서에 따라 달라질까요?

지난 글에서는 소수가 정수론의 기본 블록처럼 행동한다는 점을 봤습니다. 이제 그 말을 실제로 식과 코드 감각으로 확인해 보겠습니다. 1보다 큰 정수를 소수들의 곱으로 분해하는 과정이 소인수분해입니다.

What this post covers

• 소인수분해가 무엇인지 설명합니다.
• 몇 가지 정수를 실제로 소수들의 곱으로 분해합니다.
• 왜 이 분해가 본질적으로 하나로 정해지는지 유일성의 감각을 잡습니다.
• 다음 글에서 이 구조를 최대공약수, 최소공배수, 약수 계산에 활용합니다.

이번 글에서 새로 나오는 용어

• 소인수분해 (Prime Factorization): 정수를 소수들의 곱으로 나타내는 것입니다.
• 산술의 기본정리 (Fundamental Theorem of Arithmetic): 1보다 큰 모든 정수는 소수의 곱으로 표현되며, 그 표현은 순서를 제외하면 유일하다는 정리입니다.
• 소수 (Prime Number): 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수입니다.
• 합성수 (Composite Number): 1과 자기 자신 외의 약수를 가지는 1보다 큰 자연수입니다.

실험: 손으로 계산하기

소인수분해는 먼저 손으로 나누어 보는 감각이 중요합니다. 작은 수들을 끝까지 소수만 남을 때까지 쪼개 봅시다.

실험 1. 24를 두 가지 길로 분해하기

$$24 = 2 \times 12 = 2 \times 2 \times 6 = 2 \times 2 \times 2 \times 3 = 2^3 \times 3$$

다른 순서로 시작해도

$$24 = 3 \times 8 = 3 \times 2 \times 2 \times 2 = 2^3 \times 3$$

가 됩니다.

실험 2. 36을 분해하기

$$36 = 6 \times 6 = (2 \times 3)(2 \times 3) = 2^2 \times 3^2$$

또는

$$36 = 4 \times 9 = 2^2 \times 3^2$$

입니다.

실험 3. 몇 가지 수를 표로 정리하기

수	한 분해 과정	소인수분해
18	$18=2\times9=2\times3\times3$	$2\times3^2$
45	$45=5\times9=5\times3\times3$	$3^2\times5$
84	$84=2\times42=2\times2\times21$	$2^2\times3\times7$

패턴 발견

위 계산에서 눈여겨볼 점은 분해를 시작하는 방법이 달라도 마지막 소수들의 목록은 같다는 것입니다.

• 24는 $2,2,2,3$으로 끝납니다.
• 36은 $2,2,3,3$으로 끝납니다.
• 순서는 달라질 수 있지만 어떤 소수가 몇 번 등장하는지는 바뀌지 않습니다.

핵심 통찰은 소인수분해가 단순한 계산 과정이 아니라, 정수 안에 들어 있는 소수의 “구성표”를 드러낸다는 점입니다.

소인수분해란 무엇인가?

소인수분해는 1보다 큰 정수를 끝까지 소수의 곱으로 쪼개는 과정입니다. 소수 자체는 더 쪼개지지 않으므로, 소인수분해를 하면 결국 마지막에는 소수들만 남습니다.

예를 들어

$$12 = 2 \times 6 = 2 \times 2 \times 3 = 2^2 \times 3$$

입니다.

또

$$18 = 2 \times 9 = 2 \times 3 \times 3 = 2 \times 3^2$$

입니다.

결국 12와 18은 겉으로는 다른 수처럼 보여도, 내부에는 어떤 소수들이 몇 번 들어 있는지가 기록되어 있습니다.

예시로 구조 읽기

24의 소인수분해

$$24 = 2 \times 12 = 2 \times 2 \times 6 = 2 \times 2 \times 2 \times 3 = 2^3 \times 3$$

24는 소수 2를 세 번, 소수 3을 한 번 포함합니다.

45의 소인수분해

$$45 = 5 \times 9 = 5 \times 3^2 = 3^2 \times 5$$

45는 소수 3을 두 번, 소수 5를 한 번 포함합니다.

84의 소인수분해

$$84 = 2 \times 42 = 2^2 \times 21 = 2^2 \times 3 \times 7$$

이처럼 큰 수라도 소수의 곱으로 정리하면 내부 구조가 깔끔하게 보입니다.

왜 유일성이 중요할까?

중요한 점은 “소수의 곱으로 쓸 수 있다”에서 끝나지 않는다는 것입니다. 그 표현이 순서를 제외하면 하나로 정해진다는 점이 핵심입니다.

예를 들어 12를

• $2^2 \times 3$
• $3 \times 2 \times 2$

처럼 순서만 다르게 쓸 수는 있지만, 완전히 다른 소수들의 조합으로 바뀌지는 않습니다.

이 생각을 정식으로 말한 것이 산술의 기본정리입니다. 즉, 소인수분해는 "된다"에서 끝나는 것이 아니라, "순서를 빼면 하나로 정해진다"는 점까지 포함해야 의미가 완성됩니다.

산술의 기본정리의 의미

산술의 기본정리는 다음 두 부분으로 이루어집니다.

1. 1보다 큰 모든 정수는 소수의 곱으로 표현할 수 있다.
2. 그 표현은 순서를 제외하면 유일하다.

이 정리 덕분에 정수 하나를 소인수분해하면, 그 수의 약수 구조, 공약수 구조, 배수 구조를 체계적으로 읽을 수 있습니다.

즉, 소인수분해는 단순한 계산 기술이 아니라 정수의 “설계도”를 보는 방법입니다.

소인수분해와 최대공약수의 연결 예고

예를 들어

$$12 = 2^2 \times 3, \qquad 18 = 2 \times 3^2$$

를 보면 공통으로 들어 있는 소수는 2와 3입니다. 그중 지수가 더 작은 쪽을 취하면

$$\gcd(12,18) = 2^1 \times 3^1 = 6$$

이 됩니다.

반대로 최소공배수는 각 소수의 더 큰 지수를 취하면 됩니다.

이처럼 소인수분해는 최대공약수와 최소공배수를 읽는 강력한 도구입니다.

이론 정리

산술의 기본정리

1보다 큰 모든 정수는 소수들의 곱으로 표현할 수 있다. 또한 그 표현은 소수들의 순서를 제외하면 유일하다.

예를 들어

$$84 = 2^2 \times 3 \times 7$$

이라는 정보는 84 안에 2가 두 번, 3이 한 번, 7이 한 번 들어 있다는 뜻이다.

Python으로 확인하기

아래 코드는 작은 수를 소인수분해하고, 손계산 결과와 비교할 수 있게 출력합니다.

def prime_factorization(n):
    factors = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            factors.append(d)
            n //= d
        d += 1
    if n > 1:
        factors.append(n)
    return factors

for n in [18, 24, 36, 45, 84]:
    factors = prime_factorization(n)
    product = 1
    for p in factors:
        product *= p
    print(n, factors, product == n)

출력된 소수들의 곱이 원래 수와 같아지는지 확인해 보세요.

Common mistakes

1. 합성수에서 멈추는 실수

소인수분해는 끝까지 소수만 남을 때까지 진행해야 합니다. 예를 들어 12를 $2 \times 6$에서 멈추면 아직 끝난 것이 아닙니다.

2. 1을 소인수에 넣는 실수

1은 소수가 아니므로 소인수분해에 포함하지 않습니다.

3. 순서가 다르면 다른 분해라고 생각하는 실수

곱셈의 순서는 바뀌어도 본질은 같습니다. 유일성은 순서를 제외한 의미입니다.

Silverman 교재 연결

이 글은 Silverman 《친절한 수론 길라잡이》(경문사)의 다음 내용과 연결됩니다.

• 7장: 인수분해와 산술의 기본정리 - 정수를 소수들의 곱으로 인수분해하고, 그 표현이 순서를 제외하면 유일하다는 산술의 기본정리를 다룹니다.
• 관련 정리/예제: $84=2^2\times3\times7$처럼 인수분해한 결과는 정수의 약수 구조를 기록합니다. Silverman의 7장 제목 그대로 “인수분해”와 “산술의 기본정리”가 이 글의 핵심 배경입니다.

연습 문제

아래 점검 퀴즈에서 학습한 내용을 확인해 보세요.

Wrap-up

이번 글에서는 소인수분해를 통해 정수를 소수들의 곱으로 분해하는 방법과, 그 표현이 순서를 제외하면 유일하다는 산술의 기본정리의 감각을 정리했습니다.

다음 글에서는 이 구조를 실제 계산에 적용해, 약수의 개수와 최대공약수, 최소공배수를 더 체계적으로 읽는 방법을 보겠습니다.