[NCS 응용수리 500제 7편] 최소공배수와 최대공약수

What this post covers

최소공배수(LCM)와 최대공약수(GCD)는 응용수리의 기초 도구입니다. 소인수분해를 통해 두 수의 공통 부분과 공통이 아닌 부분을 분리하는 능력이 핵심입니다. 이 글에서는 계산 방법뿐 아니라 교재에 나오는 세 가지 대표 문제 유형(배분, 나머지, 규칙적 반복)까지 함께 다룹니다.

소인수분해로 LCM/GCD 구하기
LCM과 GCD의 관계 공식
배분 문제
나머지 문제
규칙적 반복 문제

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

소인수분해 (prime factorization): 자연수를 소수의 곱으로 나타내는 것
최소공배수 (LCM, Least Common Multiple): 두 수 이상의 공통 배수 중 가장 작은 수
최대공약수 (GCD, Greatest Common Divisor): 두 수 이상의 공통 약수 중 가장 큰 수
서로소 (coprime): 최대공약수가 1인 두 수

Core idea

소인수분해로 GCD 구하기

각 자연수를 소인수분해합니다.
공통인 소인수를 모두 곱합니다.
이때, 공통인 소인수의 지수는 같으면 그대로, 다륾 작은 것을 택하여 곱합니다.

예: $42 = 2 \times 3 \times 7$ , $70 = 2 \times 5 \times 7$

공통 소인수: 2, 7
GCD = $2 \times 7 = 14$

소인수분해로 LCM 구하기

각 자연수를 소인수분해합니다.
모든 소인수(공통인 것과 공통이 아닌 것)를 곱합니다.
이때, 같은 소인수의 지수는 큰 것을 택합니다.

예: $42 = 2 \times 3 \times 7$ , $70 = 2 \times 5 \times 7$

모든 소인수: 2, 3, 5, 7
LCM = $2 \times 3 \times 5 \times 7 = 210$

LCM과 GCD의 관계

두 자연수 $a$ , $b$ 에 대해:

a \times b = \text{GCD}(a, b) \times \text{LCM}(a, b)

이 공식은 한쪽을 알면 다른 쪽을 빠르게 구할 때 유용합니다.

세 가지 대표 문제 유형

유형	특징	핵심 아이디어
배분 문제	여러 물건을 동일한 개수로 나누기	GCD = 나누는 개수
나머지 문제	나누면 몇 개가 남거나 부족	LCM + 나머지 조정
규칙적 반복	주기가 다른 두 일이 동시에 일어남	LCM = 다음 동시 발생

Step-by-step example

예시 1: 기본 LCM/GCD

두 숫자 42와 70의 최소공배수와 최대공약수를 구하시오.

Step 1: 소인수분해

$42 = 2 \times 3 \times 7$
$70 = 2 \times 5 \times 7$

Step 2: GCD (공통 소인수의 작은 지수)

GCD = $2^1 \times 7^1 = 14$

Step 3: LCM (모든 소인수의 큰 지수)

LCM = $2^1 \times 3^1 \times 5^1 \times 7^1 = 210$

검산: $42 \times 70 = 2940$ , $14 \times 210 = 2940$ ✓

예시 2: 배분 문제

한 유치원에서 아이들에게 나누어 주기 위해 사탕 112개와 초콜릿 70개를 구매하였다. 아이들에게 각각 동일한 개수로 배분하였더니 사탕은 4개가 남고, 초콜릿은 2개가 부족하였다. 다음 중 아이들의 수가 될 수 없는 것은?

Step 1: 실제로 나누어진 개수를 구합니다.

사탕: $112 - 4 = 108$ 개
초콜릿: $70 + 2 = 72$ 개 (2개 부족이므로 72개가 필요)

Step 2: 아이들의 수는 108과 72의 공약수입니다.

GCD(108, 72) = 36
36의 약수: 1, 2, 3, 4, 6, 9, 12, 18, 36

Step 3: 선택지 중 이에 해당하지 않는 수를 찾습니다.

예시 3: 나머지 문제

길잡이 놀이공원에 있는 바이킹에는 한 열에 최대 8명까지 앉을 수 있다. 소풍을 온 어느 반 학생들이 바이킹을 타려고 한다. 한 열에 5명씩 앉으면 학생 3명이 남고, 6명씩 앉으면 1개의 열이 남는다고 할 때, 바이킹에는 최소 몇 열이 있어야 하는가?

Step 1: 조건을 식으로 세웁니다.

학생 수 = $5x + 3$ (5명씩 앉으면 3명 남음)
학생 수 = $6(x-1) + r$ ... (6명씩 앉으면 1열이 남는다는 조건 해석)

Step 2: 문제를 단순화하면 학생 수는 5로 나누면 3이 남고, 6으로 나누면 특정 조건을 만족합니다.

Step 3: LCM과 나머지 조건을 활용하여 풀이를 진행합니다.

예시 4: 규칙적 반복

A도로의 버스는 12분 간격으로, B도로의 버스는 18분 간격으로 출발한다. 오전 8시에 두 버스가 동시에 출발하였을 때, 다음에 동시에 출발하는 시각은?

Step 1: 동시 출발 주기는 LCM입니다.

LCM(12, 18) = 36분

Step 2: 다음 동시 출발 시각을 구합니다.

8시 + 36분 = 8시 36분

Common mistakes

GCD와 LCM 혼동: GCD는 공통인 것만, LCM은 모든 것을 곱합니다. 지수 선택도 GCD는 작은 것, LCM은 큰 것입니다.
소인수분해 실수: 1은 소수가 아닙니다. 51 = 3 × 17입니다 (소수가 아님).
배분 문제에서 나머지 처리 실수: 남으면 빼고, 부족하면 더해서 실제 나누어진 양을 구해야 합니다.
공식 $a \times b = \text{GCD} \times \text{LCM}$ 의 조건: 두 수에만 적용됩니다. 세 수 이상에서는 성립하지 않습니다.

🎯 문제 풀어보기

이제 위에서 배운 내용을 바탕으로 문제를 직접 풀어보세요. 최대공약수·최소공배수를 활용한 문제 해결 능력을 점검합니다.

최대공약수·최소공배수 문제풀이

정사각형 분할, 동시도착, GCD·LCM 관계 훈련

LCM/GCD

문제 1 / 3