최대공약수 계산기

계산 입력

첫 번째 수 (A)

두 번째 수 (B)

공식

Show calculation steps (1)

1. LCM (from GCD)

   

   The least common multiple is computed from the GCD as the product divided by the GCD.

결과

최대공약수

12

GCD of 48 and 36

GCD (최대공약수)	12
LCM (최소공배수)	144

최대공약수란?

두 정수의 최대공약수(GCD, Greatest Common Divisor)는 두 수를 모두 나누어떨어지게 하는 가장 큰 양의 정수를 말합니다. 영어권에서는 HCF(Highest Common Factor)라고도 부르는데, 둘은 완전히 같은 개념입니다. 예를 들어 48과 36의 최대공약수는 12입니다. 12가 두 수를 모두 나누어떨어지게 하는 가장 큰 수이기 때문이죠. 이 계산기는 그 값을 즉시 찾아 주고, 최소공배수(LCM)까지 함께 알려 줍니다.

최대공약수는 두 수가 공유하는 가장 큰 약수입니다.

계산기 사용 방법

A와 B 칸에 두 개의 정수를 입력한 뒤 결과를 확인하면 됩니다. 입력값은 절댓값으로 처리되므로 음수를 넣어도 올바르게 계산됩니다. 한쪽에 0을 입력하면, 모든 정수는 0을 나누므로 최대공약수는 나머지 한 수와 같아집니다.

유클리드 호제법 원리

이 계산기는 지금까지도 널리 쓰이는 가장 오래된 알고리즘 중 하나인 유클리드 호제법을 사용합니다. 핵심은 다음의 간단한 성질입니다: \(\gcd\left(a,\ b\right) = \gcd\left(b,\ a \bmod b\right)\). 두 수를 나눈 나머지로 큰 수를 계속 바꿔 나가다가 나머지가 0이 되면 멈추고, 마지막으로 0이 아니었던 나누는 수가 바로 최대공약수입니다. 이 방법은 소인수분해를 하지 않아도 되기 때문에 아주 큰 수에서도 매우 빠르게 동작합니다.

유클리드 호제법은 나머지가 0이 될 때까지 (a, b)를 (b, a mod b)로 반복해서 바꿉니다.

풀이 예시

gcd(48, 36)을 구해 봅시다:

$$48 \bmod 36 = 12 \rightarrow \gcd\left(36,\ 12\right)$$
$$36 \bmod 12 = 0 \rightarrow \gcd\left(12,\ 0\right) = \mathbf{12}$$

이때 최소공배수는 $$\text{lcm} = \frac{\left|48 \times 36\right|}{12} = \frac{1728}{12} = \mathbf{144}$$ 입니다.

자주 묻는 질문

GCD와 HCF는 어떻게 다른가요? 차이가 없습니다. 같은 값을 가리키는 두 가지 이름일 뿐입니다. "Greatest Common Divisor(최대공약수)"는 미국에서, "Highest Common Factor"는 영국에서 주로 쓰입니다.

서로소인 두 수의 최대공약수는 무엇인가요? 항상 1입니다. 8과 15처럼 1 외에는 공약수가 없는 두 수를 서로소(coprime) 또는 상대적으로 소수인 관계라고 합니다.

최대공약수가 작은 수보다 클 수 있나요? 아니요. 최대공약수는 두 입력값 중 작은 수를 절대 넘을 수 없습니다. 작은 수가 큰 수를 나누어떨어지게 할 때, 최대공약수는 바로 그 작은 수와 같아집니다.