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

지난 글에서 소인수분해와 산술의 기본정리를 살펴봤습니다. 이제 그 구조가 왜 강력한지 실제 계산으로 확인해 보겠습니다. 정수론에서는 단순히 답만 구하는 것보다, “왜 이런 계산이 가능하지?”라는 구조를 보는 것이 더 중요합니다.

What this post covers

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

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

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

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

예를 들어

$$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$$

입니다.

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

Common mistakes

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

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

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

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

를 선택합니다.

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

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

Wrap-up

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

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