[정수론 입문 시리즈 4편] 최대공약수와 최소공배수는 정수의 공통 구조를 어떻게 보여 줄까?

약수와 배수의 개념을 익히면 다음 질문이 자연스럽게 생깁니다. 두 수를 함께 보면 어떤 공통 구조가 드러날까? 이 질문에 가장 먼저 답하는 개념이 최대공약수와 최소공배수입니다.

최대공약수는 두 수가 함께 가지는 약수 구조를 요약하고, 최소공배수는 두 수가 함께 만나는 배수 구조를 요약합니다. 이번 글에서는 두 개념을 계산법보다 먼저 구조를 읽는 관점으로 정리하겠습니다.

What this post covers

• 최대공약수와 최소공배수의 의미를 비교합니다.
• 약수 목록과 배수 목록으로 두 개념을 직접 구해 봅니다.
• 소인수분해 관점으로 구조를 더 짧게 읽는 법을 맛봅니다.
• 왜 최대공약수가 다음 글의 유클리드 호제법으로 이어지는지 연결합니다.

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

• 최대공약수 (Greatest Common Divisor): 두 정수가 공통으로 가지는 약수들 가운데 가장 큰 수입니다.
• 최소공배수 (Least Common Multiple): 두 정수가 공통으로 가지는 배수들 가운데 가장 작은 양의 정수입니다.
• 약수 (Divisor): 어떤 수를 나머지 없이 나누게 만드는 수입니다.
• 배수 (Multiple): 어떤 수에 정수를 곱해 얻는 수입니다.

최대공약수와 최소공배수는 무엇이 다를까?

두 수 $a$, $b$를 볼 때

• 최대공약수는 두 수의 공약수 가운데 가장 큰 값
• 최소공배수는 두 수의 공배수인 양의 정수 가운데 가장 작은 값

입니다.

핵심은 무엇을 찾느냐의 차이입니다.

• 최대공약수는 두 수에 공통으로 들어 있는 약수 구조를 찾는 것
• 최소공배수는 두 수를 함께 덮는 가장 작은 배수 구조를 찾는 것

이라고 생각하면 이해가 쉽습니다.

예시 1. 12와 18의 최대공약수

먼저 각 수의 약수를 적어 봅시다.

• 12의 약수: 1, 2, 3, 4, 6, 12
• 18의 약수: 1, 2, 3, 6, 9, 18

공통으로 들어 있는 수, 즉 공약수는 1, 2, 3, 6입니다. 이 가운데 가장 큰 값은 6이므로

$$\gcd(12, 18) = 6$$

입니다.

이 값은 단순한 계산 결과가 아니라, 12와 18이 공유하는 약수 구조를 가장 크게 요약한 값입니다.

예시 2. 12와 18의 최소공배수

이번에는 배수를 적어 봅시다.

• 12의 배수: 12, 24, 36, 48, ...
• 18의 배수: 18, 36, 54, 72, ...

처음으로 만나는 공통 배수는 36입니다. 따라서

$$\mathrm{lcm}(12, 18) = 36$$

입니다.

최소공배수는 두 수가 함께 올라가다가 가장 먼저 만나는 지점이라고 볼 수 있습니다.

소인수분해로 보면 구조가 더 잘 보인다

같은 예시를 소인수분해로 보면 더 짧게 읽을 수 있습니다.

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

최대공약수

최대공약수는 두 수를 모두 나누어야 하므로, 공통으로 들어 있는 소인수만 가져오고 각 소인수의 지수도 더 작은 쪽까지만 쓸 수 있습니다.

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

최소공배수

반대로 최소공배수는 두 수를 모두 배수로 가져야 하므로, 필요한 소인수를 빠짐없이 포함해야 합니다. 그래서 각 소인수에 대해 더 큰 지수를 가져오면 됩니다.

$$\mathrm{lcm}(12,18) = 2^2 \times 3^2 = 36$$

이렇게 보면

• 최대공약수는 공통 부분의 요약
• 최소공배수는 전체를 함께 덮는 최소 구조

라는 점이 더 선명해집니다.

두 개념은 서로 연결되어 있다

양의 정수 $a$, $b$에 대해 다음 관계가 성립합니다.

$$\gcd(a,b) \times \mathrm{lcm}(a,b) = ab$$

예를 들어 12와 18에서는

$$6 \times 36 = 216 = 12 \times 18$$

이 됩니다.

이 식은 최대공약수와 최소공배수가 완전히 따로 노는 개념이 아니라는 점을 보여 줍니다.

왜 최대공약수가 더 자주 중심이 될까?

정수론에서는 최소공배수도 중요하지만, 이후의 많은 정리와 알고리즘은 최대공약수를 중심으로 전개됩니다.

그 이유는 최대공약수가

• 서로소 여부 판단
• 정수해 존재 조건
• 확장 유클리드 알고리즘과 역원 계산
• 알고리즘적 계산

과 더 직접적으로 연결되기 때문입니다.

특히 다음 글에서 볼 유클리드 호제법은 최대공약수를 매우 빠르게 계산하게 해 줍니다.

Common mistakes

1. 최대공약수와 최소공배수를 이름만 보고 헷갈리는 실수

"최대"와 "최소"는 각각

• 공약수들 중 최대
• 공배수들 중 최소

를 뜻합니다. 서로 비교하는 대상이 다릅니다.

2. 공약수와 공배수를 뒤섞는 실수

공약수는 둘 다를 나누는 수이고, 공배수는 둘 다의 배수인 수입니다. 한쪽은 나누는 방향, 다른 한쪽은 곱해서 만들어지는 방향입니다.

3. 최소공배수를 무조건 배수를 나열해서만 찾으려는 실수

초반에는 나열이 이해에 좋지만, 수가 커지면 비효율적입니다. 그래서 나중에는 소인수분해나 최대공약수와의 관계를 함께 씁니다.

Wrap-up

이번 글에서는 최대공약수가 두 정수의 공통 약수 구조를, 최소공배수가 공통 배수 구조를 요약한다는 점을 정리했습니다. 약수 목록, 배수 목록, 소인수분해 관점이 서로 어떻게 이어지는지도 확인했습니다.

다음 글에서는 최대공약수를 효율적으로 구하는 핵심 도구인 유클리드 호제법을 배우며, 왜 나머지를 반복해서 보는 방식이 강력한지 살펴보겠습니다.