최대공약수(GCD) / 최소공배수(LCM) 계산기

유클리드 호제법은 두 양의 정수 $a, b$ ($a > b$)에 대하여, $a$를 $b$로 나눈 나머지를 $r$이라고 할 때 $GCD(a, b) = GCD(b, r)$이 성립한다는 정수론의 기본 정리에 기반합니다.

나머지 $r$이 $0$이 될 때까지 나눗셈을 반복하면, 마지막으로 나누는 수(제수)가 바로 두 수의 최대공약수가 됩니다.

• 예시: $GCD(1071, 462)$ 구하기

1단계: $1071 = 462 \times 2 + 147$ $\rightarrow$ $GCD(1071, 462) = GCD(462, 147)$

2단계: $462 = 147 \times 3 + 21$ $\rightarrow$ $GCD(462, 147) = GCD(147, 21)$

3단계: $147 = 21 \times 7 + 0$ (나머지가 0이 됨)

따라서 $GCD(1071, 462) = 21$입니다.

두 양의 정수 $a$와 $b$의 곱은 항상 최대공약수와 최소공배수의 곱과 같습니다.

$$a \times b = GCD(a, b) \times LCM(a, b)$$

따라서 유클리드 호제법으로 $GCD(a, b)$를 구하면, 최소공배수는 곱셈과 나눗셈 한 번으로 즉시 계산할 수 있습니다:

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

주의: 이 아름다운 곱셈 관계식은 두 수 사이에서만 직접 성립하며, 3개 이상의 숫자($a, b, c$)에서는 $LCM(a, b, c) = LCM(LCM(a, b), c)$와 같이 순차적으로 합성하여 계산해야 합니다.

각 숫자를 소수들의 곱으로 분해(소인수분해)하면 GCD와 LCM의 의미를 시각적으로 가장 명확하게 이해할 수 있습니다.

• $24 = 2^3 \times 3^1$

• $36 = 2^2 \times 3^2$

• 최대공약수(GCD): 두 수에 공통으로 존재하는 소인수의 가장 작은 지수(min)를 선택합니다.

$GCD = 2^{\min(3, 2)} \times 3^{\min(1, 2)} = 2^2 \times 3^1 = 12$

• 최소공배수(LCM): 존재하는 모든 소인수의 가장 큰 지수(max)를 선택합니다.

$LCM = 2^{\max(3, 2)} \times 3^{\max(1, 2)} = 2^3 \times 3^2 = 8 \times 9 = 72$

• 간식과 선물세트 남김없이 똑같이 나눠주기 (최대공약수): 사과 24개와 귤 36개를 남김없이 최대한 많은 친구들에게 똑같이 나누어 주려면 몇 명에게 줄 수 있을까요? $GCD(24, 36) = 12$명이므로, 12명에게 사과 2개, 귤 3개씩 똑같이 나누어 줄 수 있습니다.

• 버스·지하철 동시 출발 및 다시 만나는 시각 (최소공배수): 8분 간격으로 오는 버스와 12분 간격으로 오는 지하철이 오전 7시에 동시에 출발했다면, 다음번에 처음으로 다시 동시에 출발하는 시각은 언제일까요? $LCM(8, 12) = 24$분이므로 24분 뒤인 오전 7시 24분에 다시 동시에 만납니다.

• 남는 공간 없이 가장 큰 정사각형 타일로 방 채우기 (최대공약수): 가로 180cm, 세로 120cm인 욕실 바닥에 타일을 쪼개지 않고 가장 큰 정사각형 타일로 꽉 채우려면? 타일 한 변의 길이는 $GCD(180, 120) = 60\text{cm}$가 되며, 가로 3장 × 세로 2장 = 총 6장의 타일이 빈틈없이 딱 들어맞습니다.

• 복용 주기가 다른 영양제와 약을 동시에 먹는 날 (최소공배수): 6일마다 먹는 영양제와 8일마다 먹는 약이 있을 때, 오늘 두 약을 함께 먹었다면 다음번에 다시 두 약을 한꺼번에 먹어야 하는 날은? $LCM(6, 8) = 24$일 뒤입니다.

• 핫도그 빵과 소시지 개수 딱 맞추기 (최소공배수): 소시지는 1팩에 10개입, 핫도그 빵은 1팩에 8개입으로 판매할 때, 남는 빵이나 소시지 없이 완벽하게 핫도그 세트를 만들려면 최소 몇 개를 사야 할까요? $LCM(10, 8) = 40$개이므로 소시지 4팩(40개)과 빵 5팩(40개)을 사면 남김없이 딱 맞아떨어집니다.

• 분수의 약분과 통분 알고리즘: 분수 $\frac{18}{24}$를 기약분수로 만들 때 분자·분모를 $GCD(18, 24) = 6$으로 나누면 $\frac{3}{4}$이 됩니다. 반대로 $\frac{1}{8} + \frac{1}{12}$을 더할 때는 분모를 $LCM(8, 12) = 24$로 통분합니다.

• 화면 종횡비(Aspect Ratio) 비율 축약: 1920×1080 해상도를 $GCD(1920, 1080) = 120$으로 나누면 $16:9$의 표준 종횡비를 도출할 수 있습니다.

• 톱니바퀴 맞물림 및 주기 동기화: 톱니 수가 15개인 바퀴와 20개인 바퀴가 처음 맞물린 위치로 다시 돌아오는 회전수는 $LCM(15, 20) = 60$개의 톱니가 지나간 후입니다.

• 현대 암호학 (RSA 공개키 생성): 두 개의 거대한 소수 $p, q$를 곱한 후, 오일러 피 함수 $\phi(n) = (p-1)(q-1)$과 서로소인 공개키 $e$를 선정할 때 유클리드 호제법을 핵심으로 사용합니다.

• 주기적 작업 스케줄러 동기화: Cron 배치 작업에서 주기가 다른 복수의 백그라운드 태스크가 동시에 실행되어 DB 락(Lock)이 걸리지 않도록 LCM 주기를 계산해 엇갈려 스케줄링합니다.

두 자연수 $a, b$의 최대공약수가 1일 때, 즉 $GCD(a, b) = 1$일 때 두 수를 서로소(Coprime / Relatively Prime)라고 합니다.

• 연속하는 두 자연수 $n$과 $n+1$은 항상 서로소입니다 (예: 14와 15, 99와 100).

• 서로 다른 두 소수는 항상 서로소입니다 (예: 13과 19).

• 두 수가 서로소이면, 그들의 최소공배수는 단순히 두 수의 곱과 같습니다: $LCM(a, b) = a \times b$.