[정수론 입문 시리즈 8편] 소수는 왜 정수론의 원자라고 불릴까?

isPrime(n) 함수를 만들 때, 왜 2부터 $n-1$까지 전부 나누어 보지 않고 $\sqrt n$까지만 확인해도 될까요?

소수 판별은 알고리즘 문제에서도 자주 나오고, 큰 수를 다루는 보안·암호 기술에서도 기본 재료가 됩니다. 이 글에서는 1보다 큰 자연수 가운데 더 이상 쪼갤 수 없는 기본 블록처럼 행동하는 수, 소수를 살펴보겠습니다.

What this post covers

• 소수와 합성수의 차이를 설명합니다.
• 왜 소수가 정수론의 기본 블록처럼 보이는지 이해합니다.
• 간단한 예시로 소수 판별 감각을 익힙니다.
• 다음 글의 소인수분해로 자연스럽게 이어집니다.

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

• 소수 (Prime Number): 1보다 큰 자연수 가운데 1과 자기 자신만을 약수로 가지는 수입니다.
• 합성수 (Composite Number): 1보다 크고, 1과 자기 자신 이외의 약수를 가지는 수입니다.
• 소인수분해 (Prime Factorization): 정수를 소수들의 곱으로 나타내는 것입니다.
• 약수 (Divisor): 어떤 정수를 나누어떨어지게 하는 수입니다.

실험: 손으로 계산하기

소수의 정의를 바로 외우기보다, 작은 수들의 약수를 직접 적어 봅시다.

실험 1. 2부터 12까지 약수 세기

수	약수	분류
2	1, 2	소수
3	1, 3	소수
4	1, 2, 4	합성수
5	1, 5	소수
6	1, 2, 3, 6	합성수
7	1, 7	소수
8	1, 2, 4, 8	합성수
9	1, 3, 9	합성수
10	1, 2, 5, 10	합성수
11	1, 11	소수
12	1, 2, 3, 4, 6, 12	합성수

실험 2. 짝수를 관찰하기

4 이상의 짝수를 몇 개 골라 보면 모두 2로 나누어집니다.

• $4=2\times2$
• $6=2\times3$
• $8=2\times4$
• $10=2\times5$
• $12=2\times6$

따라서 2를 제외한 짝수는 모두 합성수입니다.

실험 3. 홀수라고 모두 소수일까?

홀수만 따로 보면 더 조심해야 합니다.

수	계산	결론
9	$9=3\times3$	합성수
15	$15=3\times5$	합성수
17	2, 3, 4로 나누어떨어지지 않음	소수
21	$21=3\times7$	합성수
25	$25=5\times5$	합성수

패턴 발견

직접 약수를 적어 보면 다음 패턴이 보입니다.

• 소수는 약수가 정확히 두 개입니다: 1과 자기 자신.
• 합성수는 중간 약수를 가지며, 그래서 더 작은 두 수의 곱으로 쪼개집니다.
• 2는 유일한 짝수 소수입니다.
• 홀수라고 해서 자동으로 소수는 아닙니다.
• 어떤 수가 합성수라면 보통 작은 약수에서 먼저 단서가 나옵니다.

핵심 통찰은 소수가 “더 이상 곱셈으로 쪼개지지 않는 기본 블록”이라는 점입니다.

소수와 합성수

자연수 $n>1$에 대해, 약수가 1과 자기 자신뿐이면 소수입니다.

예를 들면

• 2, 3, 5, 7, 11은 소수이고
• 4, 6, 8, 9, 10, 12는 합성수입니다.

합성수는 중간에 다른 약수가 있으므로 더 작은 정수들의 곱으로 분해할 수 있습니다.

왜 소수가 특별할까?

소수는 정수를 만드는 기본 재료처럼 행동합니다.

예를 들어

• 6은 $2 \times 3$
• 12는 $2 \times 2 \times 3$
• 18은 $2 \times 3 \times 3$

처럼 쓸 수 있습니다.

즉, 합성수는 결국 소수들을 곱해서 만들어집니다. 그래서 소수를 “정수론의 원자”라고 비유하기도 합니다.

1은 왜 소수가 아닐까?

처음 배우면 자주 나오는 질문입니다. 1은 약수가 하나뿐이니 오히려 더 특별해 보이기 때문입니다.

하지만 1을 소수로 넣어 버리면 정수를 소수의 곱으로 나타내는 방식이 뒤엉킵니다. 예를 들어 6을

• $2 \times 3$
• $1 \times 2 \times 3$
• $1 \times 1 \times 2 \times 3$

처럼 끝없이 다르게 쓸 수 있기 때문입니다.

정수론은 소인수분해의 유일성을 중요하게 보므로, 1은 소수에서 제외합니다.

가장 작은 소수는 왜 2일까?

2는 유일한 짝수 소수입니다. 4 이상인 모든 짝수는 2로 나누어지므로 자기 자신과 1 외에도 약수 2를 가집니다. 따라서 짝수 가운데 소수는 2 하나뿐입니다.

이 사실은 소수 판별을 할 때도 자주 쓰입니다. 짝수인지 먼저 보고, 그다음 홀수 약수만 검사하면 되기 때문입니다.

간단한 판별 감각 익히기

15는 소수일까?

15는 3으로도 나누어지고 5로도 나누어집니다.

$$15 = 3 \times 5$$

이므로 소수가 아니라 합성수입니다.

17은 소수일까?

17은 2, 3, 4로 나누어떨어지지 않습니다. 또 $\sqrt{17}$은 4와 5 사이에 있으므로, 그보다 큰 수를 굳이 더 검사하지 않아도 됩니다. 따라서 17은 소수입니다.

21은 소수일까?

21은 3과 7의 곱이므로 합성수입니다.

$$21 = 3 \times 7$$

소수는 왜 계속 중요하게 등장할까?

소수는 단지 정의만 예쁜 수가 아닙니다.

• 정수의 구조를 분석할 때 중심이 되고
• 최대공약수와 최소공배수를 소인수분해로 이해하게 해 주며
• 나중에는 합동과 암호학에서도 핵심 역할을 합니다.

즉, 소수는 정수론의 초반, 중반, 후반에 모두 등장하는 중심 축입니다.

이론 정리

소수와 합성수

자연수 $n>1$에 대해

• $n$의 양의 약수가 1과 $n$뿐이면 $n$은 소수이다.
• $n$이 1과 자기 자신 이외의 약수를 가지면 $n$은 합성수이다.
• 1은 소수도 합성수도 아니다.
• 2는 유일한 짝수 소수이다.

소수 판별에서는 $\sqrt n$ 이하의 약수만 검사해도 충분하다.

Python으로 확인하기

아래 코드는 작은 수들의 약수를 구하고, 소수인지 합성수인지 확인합니다.

from math import isqrt

def divisors(n):
    return [d for d in range(1, n + 1) if n % d == 0]

def is_prime(n):
    if n <= 1:
        return False
    for d in range(2, isqrt(n) + 1):
        if n % d == 0:
            return False
    return True

for n in range(2, 13):
    kind = "소수" if is_prime(n) else "합성수"
    print(n, divisors(n), kind)

손으로 만든 표와 같은 결과가 나오는지 비교해 보세요.

Common mistakes

1. 1을 소수로 넣는 실수

소수는 1보다 큰 자연수입니다. 1은 소수가 아닙니다.

2. 홀수면 소수라고 생각하는 실수

9, 15, 21, 25처럼 홀수이지만 합성수인 수는 많습니다.

3. 소수 판별에서 너무 많은 수를 검사하는 실수

입문 단계에서는 모든 약수를 다 볼 필요가 없다는 감각만 잡아도 충분합니다. 작은 약수에서 이미 판별이 나는 경우가 많습니다.

Silverman 교재 연결

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

• 7장: 인수분해와 산술의 기본정리 - 소수와 합성수의 구분은 정수를 소수들의 곱으로 인수분해하고, 산술의 기본정리를 이해하기 위한 준비 단계입니다.
• 12장: 소수 - Silverman은 “소수”를 중심 주제로 다시 다루며, 소수가 무한히 많다는 고전적인 사실도 설명합니다.
• 관련 정리/예제: 1은 소수가 아니며, 소수는 1보다 큰 자연수 중 양의 약수가 1과 자기 자신뿐인 수입니다. 이 정의가 다음 글의 소인수분해와 산술의 기본정리로 이어집니다.

연습 문제

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

Wrap-up

이번 글에서는 소수가 무엇인지, 왜 합성수와 구별되는지, 그리고 왜 정수론에서 기본 블록처럼 취급되는지를 정리했습니다.

다음 글에서는 이 흐름을 이어서, 모든 정수를 소수들의 곱으로 나타내는 소인수분해와 그 유일성 아이디어를 살펴보겠습니다.