[정수론 입문 시리즈 10편] 산술의 기본정리는 실제 계산에서 어떻게 쓰일까?

약수가 12개인 수는 어떻게 빨리 찾을까요? 무작정 1부터 나누어 보는 방법도 있지만, 숫자가 커지면 금방 비효율적입니다.

지난 글에서 본 소인수분해와 산술의 기본정리를 사용하면 약수 개수, 최대공약수, 최소공배수를 훨씬 구조적으로 계산할 수 있습니다.

What this post covers

• 소인수분해로 약수의 개수를 세는 원리를 설명합니다.
• 최대공약수와 최소공배수를 소수의 지수 비교로 읽습니다.
• 하나의 분해 정보가 여러 계산을 동시에 정리해 준다는 점을 봅니다.
• 다음 단계인 합동으로 넘어가기 전, 정수의 곱셈 구조를 마무리합니다.

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

• 산술의 기본정리 (Fundamental Theorem of Arithmetic): 1보다 큰 모든 정수는 소수의 곱으로 유일하게 표현된다는 정리입니다.
• 소인수분해 (Prime Factorization): 정수를 소수들의 곱으로 나타내는 것입니다.
• 최대공약수 (Greatest Common Divisor): 두 정수의 공통 약수 중 가장 큰 수입니다.
• 최소공배수 (Least Common Multiple): 두 정수의 공통 배수 중 가장 작은 수입니다.
• 약수 (Divisor): 어떤 수를 나누어떨어지게 하는 수입니다.

실험: 손으로 계산하기

산술의 기본정리는 실제 계산에서 지수를 비교하는 도구로 바뀝니다. 먼저 작은 예시를 손으로 정리해 봅시다.

실험 1. 72의 약수 개수 세기

$$72 = 2^3 \times 3^2$$

약수를 만들려면 2의 지수와 3의 지수를 각각 고릅니다.

선택	가능한 지수
2의 지수	0, 1, 2, 3
3의 지수	0, 1, 2

따라서 선택 수는

$$(3+1)(2+1)=12$$

입니다.

실험 2. 60과 90의 지수 비교

$$60=2^2\times3^1\times5^1, \qquad 90=2^1\times3^2\times5^1$$

소수	60의 지수	90의 지수	작은 지수	큰 지수
2	2	1	1	2
3	1	2	1	2
5	1	1	1	1

작은 지수를 모으면 $\gcd(60,90)=2^1\times3^1\times5=30$이고, 큰 지수를 모으면 $\operatorname{lcm}(60,90)=2^2\times3^2\times5=180$입니다.

실험 3. 84와 126도 같은 방식으로 보기

$$84=2^2\times3\times7, \qquad 126=2\times3^2\times7$$

• 작은 지수: $2^1\times3^1\times7^1=42$
• 큰 지수: $2^2\times3^2\times7^1=252$

패턴 발견

손계산에서 다음 규칙이 반복됩니다.

• 약수의 개수는 각 소수 지수를 몇 가지로 고를 수 있는지 세면 됩니다.
• 최대공약수는 두 수에 공통으로 들어갈 수 있는 만큼만 가져오므로 작은 지수를 고릅니다.
• 최소공배수는 두 수를 모두 포함해야 하므로 큰 지수를 고릅니다.
• 같은 소인수분해 정보가 약수 개수, 최대공약수, 최소공배수를 동시에 설명합니다.

핵심 통찰은 소수의 지수가 정수의 곱셈 구조를 좌표처럼 기록한다는 점입니다.

약수의 개수는 왜 지수와 연결될까?

예를 들어

$$72 = 2^3 \times 3^2$$

라고 합시다.

72의 약수를 만들려면 소수 2는

• $2^0$, $2^1$, $2^2$, $2^3$

중 하나를 고를 수 있고, 소수 3은

• $3^0$, $3^1$, $3^2$

중 하나를 고를 수 있습니다.

여기서 중요한 점은 소수 2의 지수 선택과 소수 3의 지수 선택이 서로 독립적이라는 것입니다. 그래서 경우의 수를 곱해서 셀 수 있습니다.

따라서 약수의 개수는

$$(3+1)(2+1) = 12$$

개입니다.

핵심은 각 소수의 지수를 “몇 가지 선택할 수 있는가”로 읽는 것입니다.

최대공약수는 왜 작은 지수를 고를까?

예를 들어

$$60 = 2^2 \times 3 \times 5$$ $$90 = 2 \times 3^2 \times 5$$

입니다.

공통으로 들어 있는 소수는 2, 3, 5입니다. 그런데 최대공약수는 두 수에 모두 들어 있어야 하므로, 각 소수의 지수는 더 작은 쪽을 따라야 합니다.

따라서

$$\gcd(60,90) = 2^1 \times 3^1 \times 5^1 = 30$$

입니다.

즉, 최대공약수는 “공통 부분만 모은 값”입니다. 두 수에 모두 들어 있는 만큼만 가져올 수 있기 때문에 작은 지수를 고르게 됩니다.

최소공배수는 왜 큰 지수를 고를까?

반대로 최소공배수는 두 수를 모두 나누어떨어지게 해야 합니다. 그러려면 필요한 소수 지수를 충분히 담아야 하므로, 각 소수에 대해 더 큰 지수를 골라야 합니다.

따라서

$$\operatorname{lcm}(60,90) = 2^2 \times 3^2 \times 5 = 180$$

입니다.

즉, 최소공배수는 “둘을 모두 덮는 최소한의 값”입니다. 두 수를 모두 배수로 가져야 하므로 필요한 소수 지수를 충분히 담아야 해서 큰 지수를 고르게 됩니다.

한 번의 분해로 여러 정보를 얻는다

소인수분해가 강력한 이유는 하나의 정보가 여러 계산을 동시에 정리해 주기 때문입니다.

예를 들어 60의 소인수분해

$$60 = 2^2 \times 3 \times 5$$

만 알아도

• 약수의 개수
• 어떤 수와의 최대공약수
• 어떤 수와의 최소공배수

를 구조적으로 읽을 수 있습니다.

그래서 정수론에서는 소인수분해가 “계산 편법”이 아니라 “구조 해석 도구”로 쓰입니다.

예시 정리

다음 두 수를 보겠습니다.

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

그러면

$$\gcd(84,126) = 2^1 \times 3^1 \times 7^1 = 42$$

이고,

$$\operatorname{lcm}(84,126) = 2^2 \times 3^2 \times 7 = 252$$

입니다.

각 소수의 지수를 작은 쪽/큰 쪽으로 비교하는 규칙만 알면 계산이 훨씬 체계적으로 바뀝니다.

이론 정리

소인수분해의 계산 활용

$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$이면 약수의 개수는

$$(a_1+1)(a_2+1)\cdots(a_k+1)$$

이다.

두 수의 소인수분해에서 같은 소수의 지수를 비교하면

• 최대공약수: 각 소수의 작은 지수
• 최소공배수: 각 소수의 큰 지수

를 선택한다.

Python으로 확인하기

아래 코드는 소인수분해를 이용해 약수의 개수, 최대공약수, 최소공배수를 확인합니다.

from math import gcd

def factor_counts(n):
    counts = {}
    d = 2
    while d * d <= n:
        while n % d == 0:
            counts[d] = counts.get(d, 0) + 1
            n //= d
        d += 1
    if n > 1:
        counts[n] = counts.get(n, 0) + 1
    return counts

def divisor_count(n):
    total = 1
    for exponent in factor_counts(n).values():
        total *= exponent + 1
    return total

def lcm(a, b):
    return a * b // gcd(a, b)

print(factor_counts(72), divisor_count(72))
print(gcd(60, 90), lcm(60, 90))
print(gcd(84, 126), lcm(84, 126))

손으로 구한 $12$, $30$, $180$, $42$, $252$가 출력되는지 확인해 보세요.

Common mistakes

1. 약수의 개수 공식만 외우는 실수

$(a+1)(b+1)$ 같은 형태는 지수 선택의 개수를 세는 원리에서 나온 것입니다. 원리를 이해해야 응용이 쉬워집니다.

2. 최대공약수와 최소공배수에서 작은 지수와 큰 지수를 뒤바꾸는 실수

• 최대공약수: 작은 지수
• 최소공배수: 큰 지수

를 선택합니다.

3. 소인수분해 없이 감으로만 계산하는 실수

작은 수에서는 감으로도 되지만, 숫자가 커지면 구조를 놓치기 쉽습니다. 소인수분해는 계산을 안정적으로 만들어 줍니다.

Silverman 교재 연결

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

• 7장: 인수분해와 산술의 기본정리 - 산술의 기본정리를 계산 도구로 사용해 약수의 개수, 최대공약수, 최소공배수를 소수 지수 비교로 정리합니다.
• 관련 정리/예제: 소인수분해 $n=p_1^{a_1}\cdots p_k^{a_k}$에서 약수의 개수는 지수 선택으로 세고, 두 수의 $\gcd$와 $\mathrm{lcm}$은 각 소수 지수의 최솟값과 최댓값으로 계산합니다.

연습 문제

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

Wrap-up

이번 글에서는 산술의 기본정리를 실제 계산에 적용해, 약수의 개수와 최대공약수, 최소공배수를 구조적으로 읽는 방법을 정리했습니다.

다음 글부터는 시리즈의 세 번째 큰 축인 합동으로 넘어가, 정수를 “나머지의 세계”에서 바라보는 관점을 시작하겠습니다.