최대공약수 계산기란?
최대공약수(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 — 소인수분해
- 각 숫자를 소수의 곱으로 나타내세요. 예: \(24 = 2^3 \cdot 3\) 그리고 \(36 = 2^2 \cdot 3^2\).
- 모든 소인수분해에 나타나는 소수만 유지하세요. 여기서 둘 다 2와 3을 포함합니다.
- 각 공유 소수에 숫자 전체에서 가장 낮은 지수를 부여하세요: \(2^{\min(3,2)} = 2^2\) 그리고 \(3^{\min(1,2)} = 3^1\).
- 그 전체를 곱하세요: $$\gcd(24,36) = 2^2 \cdot 3 = 4 \cdot 3 = \text{12}$$ 따라서 최대공약수는 12입니다.
- 모든 숫자가 공유하는 소수가 없으면 최대공약수는 1입니다.
방법 2 — 유클리드 호제법 (큰 숫자에 가장 좋음)
유클리드 호제법은 소인수분해를 완전히 피합니다. 이는 \(\gcd(a,b) = \gcd(b,\; a \bmod b)\)라는 사실에 기반합니다.
- 더 큰 숫자를 더 작은 숫자로 나누고 나머지를 유지하세요.
- 더 큰 숫자를 더 작은 숫자로 바꾸고, 더 작은 숫자를 나머지로 바꾸세요.
- 나머지가 0이 될 때까지 반복하세요. 마지막 0이 아닌 나머지가 최대공약수입니다.
\(\gcd(1071, 462)\)의 경우:
- \(1071 = 2 \times 462 + 147\)
- \(462 = 3 \times 147 + 21\)
- \(147 = 7 \times 21 + 0\)
- 나머지 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입니다.
유클리드 호제법으로 확인:
- \(25 = 1 \times 14 + 11\)
- \(14 = 1 \times 11 + 3\)
- \(11 = 3 \times 3 + 2\)
- \(3 = 1 \times 2 + 1\)
- \(2 = 2 \times 1 + 0\)
마지막 0이 아닌 나머지는 1이므로 \(\gcd(14,25) = 1\)이고 이 숫자들은 서로소입니다. \(\tfrac{14}{25}\)와 같은 분수는 따라서 이미 기약분수입니다.
예제 2 — 분수 84/126 약분하기
- 양쪽을 인수분해하세요: \(84 = 2^2 \cdot 3 \cdot 7\), \(126 = 2 \cdot 3^2 \cdot 7\).
- 가장 낮은 지수의 공유 소수: \(2^1 \cdot 3^1 \cdot 7^1\).
- 곱하세요: \(2 \cdot 3 \cdot 7 = 42\), 따라서 최대공약수는 42입니다.
- 분자와 분모를 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)\)가 됩니다. 이제 왼쪽에서 오른쪽으로 폴드합니다.
- \(\gcd(18,45)\): \(45 = 2 \times 18 + 9\), 그 다음 \(18 = 2 \times 9 + 0\) → 최대공약수는 9입니다.
- 세 번째 숫자를 포함시키세요: \(\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)\) 사용:
- \(\gcd(48,72)\): \(72 = 1 \times 48 + 24\); \(48 = 2 \times 24 + 0\) → 24.
- \(\gcd(24,120)\): \(120 = 5 \times 24 + 0\) → 24.
- \(\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, 18 | GCF = 6 |
| 0 포함 (0과 12) | 0, 12 | GCF = 12 |
2026-11-08 확인
자주 묻는 질문
숫자를 하나만 입력해도 되나요? 네, 됩니다. 한 수의 최대공약수는 그 수 자체입니다. 자기 자신이 곧 가장 큰 약수이기 때문이죠.
음수도 넣을 수 있나요? 가능합니다. 다만 최대공약수는 항상 양수로 표시됩니다. 나누어떨어지는지 여부는 부호와 상관없기 때문입니다. 예를 들어 \(\gcd(-8, 12) = 4\)입니다.
소수를 입력했는데 왜 무시되었나요? 이 계산기는 정수만 읽어 들입니다. 소수점이 포함된 값이나 숫자가 아닌 문자는 계산 전에 모두 걸러지므로, 정수를 쉼표로 구분해 입력해 주세요.