최대공약수(GCF) 계산기

최대공약수(GCF) 계산기

선두 AI Skill PRO

계산 입력

공식

GCF=gcd⁡(숫자)\text{GCF} = \gcd\left(\text{숫자}\right)
사용 통계

광고

결과

최대공약수
12
소인수분해
24 23 × 3
36 22 × 32
공통 소인수 22 × 3 = 12

이 페이지의 오류 신고

최대공약수 계산기란?

최대공약수(GCF, Greatest Common Factor)는 최대공약수(GCD, 최대공통제수)라고도 불리며, 입력한 모든 수를 나머지 없이 나누는 가장 큰 자연수를 말합니다. 이 계산기는 입력한 정수 목록을 받아, 그 수들이 공통으로 가지는 가장 큰 약수를 즉시 알려줍니다. 분수 약분, 비율 정리, 인수분해 문제 풀이, 수량을 똑같은 묶음으로 나눌 때 등 다양한 상황에서 유용하게 쓰입니다.

사용 방법

입력 칸은 숫자(numbers) 하나뿐입니다. 둘 이상의 정수를 쉼표로 구분해 입력하세요. 예를 들어 24, 36, 60처럼 적으면 됩니다. 그러면 계산기는 다음 과정을 거칩니다.

  • 입력한 텍스트를 쉼표 기준으로 나누고, 불필요한 공백을 제거합니다.
  • 유효한 정수만 남깁니다. -?\d+ 패턴과 일치하는 값만 인식하므로 음수는 허용되지만, 소수·분수·잘못된 문자는 무시됩니다.
  • 유효한 모든 수의 최대공약수를 계산해 결과를 보여줍니다.

정수가 아닌 입력은 자동으로 걸러지므로, 쉼표로 깔끔하게 구분한 목록을 입력해야 가장 정확한 답을 얻을 수 있습니다.

계산에 쓰이는 원리

이 계산기는 가능한 모든 약수를 일일이 시험하지 않습니다. 대신 두 수씩 유클리드 호제법을 적용하면서 목록 전체를 차례로 "접어 나가는" 방식을 씁니다. 쉽게 말하면 다음과 같이 계산합니다.

$$\text{GCF} = \gcd\left(\text{Numbers}\right)$$
  • 먼저 전통적인 호제법으로 \(\gcd(a, b)\)를 구합니다.
  • 그다음 GCF(그 결과, c), 다시 GCF(그 결과, d) … 이렇게 목록 끝까지 이어 갑니다.

이 방법이 통하는 이유는, 여러 수의 최대공약수가 곧 '지금까지의 결과'와 '다음 수'의 최대공약수와 같기 때문입니다. 효율적이고 수학적으로 검증된 방법입니다.

광고
두 수를 소인수로 분해하고 공통 인수를 강조한 그림
최대공약수는 모든 수가 공유하는 소인수들의 곱입니다.

예제로 따라 하기

24, 36, 60을 입력했다고 해 봅시다.

  • \(\gcd(24, 36) = 12\)
  • \(\gcd(12, 60) = 12\)

따라서 계산기는 12를 결과로 내놓습니다. 직접 확인해 볼까요? \(24 \div 12 = 2\), \(36 \div 12 = 3\), \(60 \div 12 = 5\)로 모두 정수가 되고, 12보다 큰 수로는 세 수를 동시에 나눌 수 없습니다.

두 수의 소인수를 나타낸 벤 다이어그램으로, 겹치는 부분이 최대공약수
공통 소인수는 겹치는 부분에 있으며, 그 곱이 최대공약수입니다.

손으로 최대공약수(GCF)를 찾는 방법

정수 집합의 최대공약수(GCF)는 그들 모두를 나머지 없이 나누는 가장 큰 양의 정수입니다. 세 가지 손 방법은 같은 답을 제공합니다. 당신의 숫자의 크기에 맞는 방법을 선택하세요.

방법 1 — 소인수분해

  1. 각 숫자를 소수의 곱으로 나타내세요. 예: \(24 = 2^3 \cdot 3\) 그리고 \(36 = 2^2 \cdot 3^2\).
  2. 모든 소인수분해에 나타나는 소수만 유지하세요. 여기서 둘 다 2와 3을 포함합니다.
  3. 각 공유 소수에 숫자 전체에서 가장 낮은 지수를 부여하세요: \(2^{\min(3,2)} = 2^2\) 그리고 \(3^{\min(1,2)} = 3^1\).
  4. 그 전체를 곱하세요: $$\gcd(24,36) = 2^2 \cdot 3 = 4 \cdot 3 = \text{12}$$ 따라서 최대공약수는 12입니다.
  5. 모든 숫자가 공유하는 소수가 없으면 최대공약수는 1입니다.

방법 2 — 유클리드 호제법 (큰 숫자에 가장 좋음)

유클리드 호제법은 소인수분해를 완전히 피합니다. 이는 \(\gcd(a,b) = \gcd(b,\; a \bmod b)\)라는 사실에 기반합니다.

  1. 더 큰 숫자를 더 작은 숫자로 나누고 나머지를 유지하세요.
  2. 더 큰 숫자를 더 작은 숫자로 바꾸고, 더 작은 숫자를 나머지로 바꾸세요.
  3. 나머지가 0이 될 때까지 반복하세요. 마지막 0이 아닌 나머지가 최대공약수입니다.

\(\gcd(1071, 462)\)의 경우:

  1. \(1071 = 2 \times 462 + 147\)
  2. \(462 = 3 \times 147 + 21\)
  3. \(147 = 7 \times 21 + 0\)
  4. 나머지 0에 도달했으므로 마지막 0이 아닌 나머지인 21이 최대공약수입니다.

방법 3 — 인수 나열하기 (작은 숫자만)

각 숫자의 모든 인수를 써서, 공유하는 인수들에 동그라미를 그리고, 가장 큰 것을 선택하세요. 18의 인수: 1, 2, 3, 6, 9, 18. 30의 인수: 1, 2, 3, 5, 6, 10, 15, 30. 공약수: 1, 2, 3, 6 → 최대공약수 = 6. 이는 신뢰할 수 있지만 숫자가 두 자리를 초과하면 느립니다.

3개 이상의 숫자 — 폴드 규칙

최대공약수는 결합법칙이 성립하므로 긴 목록을 한 번에 두 숫자씩 줄일 수 있습니다:

$$\gcd(a,b,c) = \gcd\bigl(\gcd(a,b),\, c\bigr)$$

예를 들어, \(\gcd(30, 42, 70)\): 먼저 \(\gcd(30,42) = 6\), 그 다음 \(\gcd(6,70) = 2\). 폴드의 순서는 결과를 변경하지 않습니다. 각 폴드는 현재 값을 줄일 수만 있으므로 현재 최대공약수가 1에 도달하는 순간 조기에 중단할 수 있습니다.

부호는 중요하지 않습니다: 나누어떨어짐은 부호를 무시하므로 \(\gcd(-a,b) = \gcd(a,b)\)이고 최대공약수는 항상 양수로 보고됩니다.

주요 용어 및 정의

용어 정의
인수 (약수) 다른 정수를 나머지 0으로 정확히 나누는 정수입니다. 예를 들어, 7은 42의 인수입니다. \(42 = 7 \times 6\)이기 때문입니다.
공약수 집합의 모든 숫자의 인수인 숫자입니다. 1은 정수의 임의 집합의 공약수입니다.
최대공약수 (GCF) 집합의 모든 숫자를 나누는 가장 큰 양의 정수입니다. 최대공약수 (GCD)라고도 하며, 영국 및 인도 교과서에서는 최고공약수 (HCF)라고도 부릅니다. 세 이름은 정확히 같은 의미입니다.
소수 1보다 큰 정수로서 유일한 양의 인수는 1과 자신입니다: 2, 3, 5, 7, 11, 13, … 1은 소수가 아닙니다.
합성수 1보다 큰 정수로 소수가 아닙니다. 즉, 1과 자신 이외의 인수를 적어도 하나 가지고 있습니다.
소인수분해 숫자를 소수의 곱으로 나타내는 것입니다. 예: \(360 = 2^3 \cdot 3^2 \cdot 5\). 산술의 기본 정리에 의해 이 분해는 인수의 순서를 제외하고는 유일합니다.
서로소 최대공약수가 1인 둘 이상의 숫자입니다. 예를 들어 14와 25. 둘 다 소수일 필요는 없지만 공약수를 공유하지 않습니다.
최소공배수 (LCM) 집합의 모든 숫자가 나누어떨어지는 가장 작은 양의 정수입니다. 예: \(\operatorname{lcm}(4,6) = 12\).
기약분수 분수의 분자와 분모의 최대공약수가 1일 때 분수가 기약분수입니다.

외우기 가치가 있는 두 가지 항등식

어떤 두 개의 0이 아닌 정수 \(a\)와 \(b\)에 대해, 최대공약수와 최소공배수의 곱은 곱의 절댓값과 같습니다:

$$\gcd(a,b) \times \operatorname{lcm}(a,b) = |a \times b|$$

따라서 최대공약수를 알면 최소공배수는 무료로 얻습니다: \(a = 24\), \(b = 36\) 그리고 \(\gcd = 12\)일 때, \(\operatorname{lcm} = (24 \times 36) / 12 = 864 / 12 = 72\)를 얻습니다. 주의: 이 항등식은 두 숫자에만 성립합니다 — 세 개 이상으로 변경되지 않습니다.

두 번째 항등식은 0을 처리합니다: 모든 정수는 0을 나누므로

$$\gcd(a, 0) = |a|, \qquad \gcd(0,0) = 0$$

이것이 목록에 0을 추가해도 답이 변경되지 않는 이유이며, \(\gcd(0,0)\)이 관례상 0으로 정의되는 이유입니다.

광고

더 많은 풀이된 예제

예제 1 — 서로소 쌍: gcd(14, 25)

소인수분해: \(14 = 2 \cdot 7\) 그리고 \(25 = 5^2\). 두 목록은 소수를 공유하지 않으므로 유일한 공약수는 1입니다.

유클리드 호제법으로 확인:

  1. \(25 = 1 \times 14 + 11\)
  2. \(14 = 1 \times 11 + 3\)
  3. \(11 = 3 \times 3 + 2\)
  4. \(3 = 1 \times 2 + 1\)
  5. \(2 = 2 \times 1 + 0\)

마지막 0이 아닌 나머지는 1이므로 \(\gcd(14,25) = 1\)이고 이 숫자들은 서로소입니다. \(\tfrac{14}{25}\)와 같은 분수는 따라서 이미 기약분수입니다.

예제 2 — 분수 84/126 약분하기

  1. 양쪽을 인수분해하세요: \(84 = 2^2 \cdot 3 \cdot 7\), \(126 = 2 \cdot 3^2 \cdot 7\).
  2. 가장 낮은 지수의 공유 소수: \(2^1 \cdot 3^1 \cdot 7^1\).
  3. 곱하세요: \(2 \cdot 3 \cdot 7 = 42\), 따라서 최대공약수는 42입니다.
  4. 분자와 분모를 42로 나누세요: $$\frac{84}{126} = \frac{84 \div 42}{126 \div 42} = \frac{2}{3}$$

\(\gcd(2,3) = 1\)이므로 결과는 완전히 약분되었습니다. 최대공약수보다 작은 수 — 예를 들어 6으로 나누면 \(\tfrac{14}{21}\)이 됩니다 — 여전히 할 일이 남아있습니다.

예제 3 — 음수가 포함된 혼합 집합: gcd(−18, 45, 9)

부호는 먼저 제거됩니다. 나누어떨어짐이 부호에 의존하지 않기 때문입니다: 작업은 \(\gcd(18, 45, 9)\)가 됩니다. 이제 왼쪽에서 오른쪽으로 폴드합니다.

  1. \(\gcd(18,45)\): \(45 = 2 \times 18 + 9\), 그 다음 \(18 = 2 \times 9 + 0\) → 최대공약수는 9입니다.
  2. 세 번째 숫자를 포함시키세요: \(\gcd(9, 9) = 9\).

따라서 \(\gcd(-18, 45, 9) = \) 9입니다. 입력 중 하나가 음수였음에도 불구하고 답은 양수이며, 여기서 최대공약수는 입력 중 하나와 같습니다 — 이는 한 숫자가 다른 모든 숫자를 나눌 때 항상 발생합니다.

예제 4 — 네 개의 숫자: gcd(48, 72, 120, 180)

소인수분해로. 각각을 인수분해하세요:

숫자 소인수분해 2의 거듭제곱 3의 거듭제곱 5의 거듭제곱
48 \(2^4 \cdot 3\) \(2^4\) \(3^1\) —
72 \(2^3 \cdot 3^2\) \(2^3\) \(3^2\) —
120 \(2^3 \cdot 3 \cdot 5\) \(2^3\) \(3^1\) \(5^1\)
180 \(2^2 \cdot 3^2 \cdot 5\) \(2^2\) \(3^2\) \(5^1\)

소수 5는 48과 72에서 누락되었으므로 제외됩니다. 가장 낮은 지수의 공유 소수는

$$\gcd(48,72,120,180) = 2^2 \cdot 3 = 4 \cdot 3 = 12$$

유클리드 폴드로. \(\gcd(a,b,c,d) = \gcd(\gcd(\gcd(a,b),c),d)\) 사용:

  1. \(\gcd(48,72)\): \(72 = 1 \times 48 + 24\); \(48 = 2 \times 24 + 0\) → 24.
  2. \(\gcd(24,120)\): \(120 = 5 \times 24 + 0\) → 24.
  3. \(\gcd(24,180)\): \(180 = 7 \times 24 + 12\); \(24 = 2 \times 12 + 0\) → 12.

두 경로 모두 동의합니다: 최대공약수는 12입니다. 나누어서 답을 건전성 검사하세요: 48/12 = 4, 72/12 = 6, 120/12 = 10, 180/12 = 15 — 모두 정수이고, \(\gcd(4,6,10,15) = 1\)이므로 더 큰 값을 놓치지 않았음을 확인합니다.

계산 규칙과 경계 사례

아래 사례는 모두 이 계산기로 실제 계산한 것이며, 결과 열은 계산기가 실제로 돌려준 값입니다.

사례입력결과
음수 포함 (−12와 18)-12, 18GCF = 6
0 포함 (0과 12)0, 12GCF = 12

2026-11-08 확인

자주 묻는 질문

숫자를 하나만 입력해도 되나요? 네, 됩니다. 한 수의 최대공약수는 그 수 자체입니다. 자기 자신이 곧 가장 큰 약수이기 때문이죠.

음수도 넣을 수 있나요? 가능합니다. 다만 최대공약수는 항상 양수로 표시됩니다. 나누어떨어지는지 여부는 부호와 상관없기 때문입니다. 예를 들어 \(\gcd(-8, 12) = 4\)입니다.

소수를 입력했는데 왜 무시되었나요? 이 계산기는 정수만 읽어 들입니다. 소수점이 포함된 값이나 숫자가 아닌 문자는 계산 전에 모두 걸러지므로, 정수를 쉼표로 구분해 입력해 주세요.

최종 업데이트:

수학 및 통계 인기 계산기

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