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

두 시계나 타이머가 동시에 0을 가리키려면 몇 시간 후일까요? 예를 들어 한 알림은 12분마다, 다른 알림은 18분마다 울린다면 둘이 다시 동시에 울리는 첫 순간은 36분 뒤입니다. 이게 바로 최소공배수의 감각입니다.

반대로 두 주기를 더 작은 공통 단위로 쪼개고 싶을 때는 최대공약수를 봅니다. 최대공약수는 두 수가 함께 가지는 약수 구조를 요약하고, 최소공배수는 두 수가 함께 만나는 배수 구조를 요약합니다. 이번 글에서는 두 개념을 계산법보다 먼저 구조를 읽는 관점으로 정리하겠습니다.

What this post covers

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

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

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

작은 실험: 12와 18을 나란히 보기

먼저 12와 18을 직접 비교해 봅시다.

• 12의 약수: 1, 2, 3, 4, 6, 12
• 18의 약수: 1, 2, 3, 6, 9, 18
• 12의 배수: 12, 24, 36, 48, ...
• 18의 배수: 18, 36, 54, 72, ...

약수 목록에서는 공통으로 들어 있는 가장 큰 수가 6이고, 배수 목록에서는 처음으로 함께 만나는 수가 36입니다.

패턴에서 용어로

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

이 됩니다.

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

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

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

그 이유는 최대공약수가

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

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

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

실험: 손으로 계산하기

최대공약수와 최소공배수는 먼저 목록을 직접 적어 보면 의미가 분명해집니다.

실험 1. 16과 24의 공약수

수	양의 약수
16	1, 2, 4, 8, 16
24	1, 2, 3, 4, 6, 8, 12, 24

공통 약수는 1, 2, 4, 8이고, 그중 가장 큰 수는 8입니다.

$\gcd(16,24)=8$

실험 2. 16과 24의 공배수

수	처음 몇 개의 양의 배수
16	16, 32, 48, 64, 80, ...
24	24, 48, 72, 96, ...

처음으로 만나는 공통 배수는 48입니다.

$\mathrm{lcm}(16,24)=48$

실험 3. 곱과 비교하기

$8 \times 48 = 384, \qquad 16 \times 24 = 384$

두 값이 같다는 사실도 직접 확인할 수 있습니다.

패턴 발견

목록을 적어 보면 최대공약수와 최소공배수의 방향이 서로 다르다는 점이 보입니다.

• 최대공약수는 두 수 안에 공통으로 들어 있는 가장 큰 약수입니다.
• 최소공배수는 두 수가 함께 도달하는 가장 작은 양의 배수입니다.
• 공약수는 아래로 내려가며 나누는 구조를 봅니다.
• 공배수는 위로 올라가며 곱해지는 구조를 봅니다.
• 양의 정수에서는 $\gcd(a,b)\mathrm{lcm}(a,b)=ab$ 관계가 성립합니다.

이 패턴 때문에 두 수 중 하나만 알면 다른 하나를 더 빠르게 구할 수 있습니다.

이론 정리

최대공약수와 최소공배수

양의 정수 $a,b$에 대해

• $\gcd(a,b)$: $a,b$를 모두 나누는 수 중 가장 큰 수
• $\mathrm{lcm}(a,b)$: $a,b$의 공배수 중 가장 작은 양의 정수

또한 $\gcd(a,b) \times \mathrm{lcm}(a,b) = ab$입니다.

Python으로 확인하기

Python의 math.gcd를 사용하면 최대공약수를 구할 수 있고, 최소공배수는 곱과 최대공약수의 관계로 확인할 수 있습니다.

from math import gcd

pairs = [(16, 24), (12, 18), (21, 35)]

for a, b in pairs:
    g = gcd(a, b)
    l = a * b // g
    print(f"a={a}, b={b}, gcd={g}, lcm={l}, check={g * l == a * b}")

출력에서 check=True가 나오면 $\gcd(a,b)\mathrm{lcm}(a,b)=ab$ 관계가 확인된 것입니다.

Common mistakes

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

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

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

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

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

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

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

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

Silverman 교재 연결

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

• 5장: 가약성과 최대공약수 - 최대공약수 $\gcd(a,b)$를 공약수 가운데 가장 큰 수로 정의하고, 가약성의 관점에서 두 정수의 공통 구조를 읽습니다.
• 관련 정리/예제: 최소공배수와의 관계 $\gcd(m,n)\cdot\mathrm{lcm}(m,n)=mn$은 Silverman 5장의 연습문제 5.4와 연결됩니다. 이 관계는 최대공약수와 최소공배수가 같은 약수·배수 구조를 서로 다른 방향에서 읽는다는 점을 보여 줍니다.

연습 문제

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

Wrap-up

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

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