최대공약수 계산기

최대공약수 계산기

성장 중 AI Skill PRO

계산 입력

공식

gcd⁡(A,B)=gcd⁡(B,AmodB)\gcd\left(\text{A},\ \text{B}\right) = \gcd\left(\text{B},\ \text{A} \bmod \text{B}\right)
계산 단계 보기 (1)
  1. LCM (GCD로부터 계산)

    lcm=|A|×|B|gcd⁡(A,B)\text{lcm} = \frac{\left|\text{A}\right| \times \left|\text{B}\right|}{\gcd\left(\text{A},\ \text{B}\right)}

    최소공배수는 두 수의 곱을 최대공약수로 나누어 구합니다.

사용 통계

광고

결과

최대공약수
12
GCD(48, 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이 될 때까지 나누고 값을 바꾸는 유클리드 호제법을 보여주는 순서도 루프
유클리드 호제법은 나머지가 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) 또는 상대적으로 소수인 관계라고 합니다.

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

최종 업데이트:

수학 및 통계 인기 계산기

수학 및 통계 계산기 전체 보기