공약수란 무엇인가요?
공약수(공통 약수)란 두 정수를 모두 나머지 없이 나누어떨어지게 하는 수를 말합니다. 예를 들어 6은 12와 18을 모두 깔끔하게 나누므로, 6은 12와 18의 공약수입니다. 모든 양의 정수 쌍은 적어도 하나의 공약수를 가지는데, 바로 1입니다. 이 계산기는 어떤 두 수에 대해서도 공약수 전체 목록과 함께 최대공약수(GCF)를 찾아줍니다.
계산기 사용법
\(a\)와 \(b\)로 표시된 칸에 두 정수를 입력하면 결과가 바로 표시됩니다. 상단 결과 박스에는 모든 공약수가 크기 순으로 나열되고, 아래 표에는 공약수의 개수와 함께 목록 중 가장 큰 수인 최대공약수(GCF)가 강조되어 나타납니다. 어떤 양의 정수에도 사용할 수 있으며, 분수 약분이나 인수분해, 정수론 과제 풀이에 유용합니다.
공식 풀이
이 계산기는 1부터 두 수 중 작은 값까지 각 정수 \(d\)를 차례로 확인합니다. \(a \bmod d = 0\)이면서 동시에 \(b \bmod d = 0\)일 때, 즉 두 나눗셈 모두 나머지가 0일 때 그 \(d\)는 공약수가 됩니다.
$$\text{Common factors} = \{\, d : a \bmod d = 0 \;\text{and}\; b \bmod d = 0 \,\}$$이렇게 조건을 만족하는 값을 모두 모으면 공약수 집합이 되고, 그중 가장 큰 값이 최대공약수(GCF)입니다.
$$\text{GCF}(a,b) = \max\{\, d : a \bmod d = 0,\; b \bmod d = 0 \,\}$$예제로 살펴보기
\(a = 12\), \(b = 18\)인 경우를 살펴봅시다. 12의 약수는 1, 2, 3, 4, 6, 12이고, 18의 약수는 1, 2, 3, 6, 9, 18입니다. 두 목록에 공통으로 나타나는 수는 1, 2, 3, 6입니다. 따라서 공약수는 4개이고, 최대공약수는 6입니다.
손으로 공약수 찾는 방법
두 자연수 \(a\)와 \(b\)의 공약수는 두 수를 나머지 없이 나누는 양의 정수입니다. 아래는 48과 18을 예로 든 단계별 방법입니다.
- 각 수의 약수를 모두 구합니다. 1부터 \(\lfloor\sqrt{n}\rfloor\)까지의 자연수 \(d\)를 차례로 나누어 봅니다. \(d\)가 \(n\)을 나누면 \(d\)와 \(n/d\)를 모두 적습니다. 48의 경우(\(\sqrt{48}\approx 6.93\), 따라서 1부터 6까지 시험): 1×48, 2×24, 3×16, 4×12, 6×8이므로 1, 2, 3, 4, 6, 8, 12, 16, 24, 48입니다. 18의 경우(\(\sqrt{18}\approx 4.24\), 따라서 1부터 4까지 시험): 1×18, 2×9, 3×6이므로 1, 2, 3, 6, 9, 18입니다.
- 공통으로 나타나는 약수에 동그라미를 칩니다. 두 목록에 모두 나타나는 약수는 1, 2, 3, 6입니다.
- 가장 큰 공통 약수가 최대공약수(GCF)입니다. 여기서 최대공약수는 6입니다.
지름길: 먼저 최대공약수 구하기
소인수분해: 48 = 24 · 3, 18 = 2 · 32입니다. 공통인 소수는 가장 낮은 거듭제곱으로 취합니다: 21 · 31 = 6.
유클리드 호제법: 큰 수를 작은 수로 나눈 나머지로 계속 바꾸고, 나머지가 0이 될 때까지 반복합니다. 마지막으로 0이 아닌 나머지가 최대공약수입니다.
$$48 = 2 \times 18 + 12$$
$$18 = 1 \times 12 + 6$$
$$12 = 2 \times 6 + 0$$
마지막으로 0이 아닌 나머지는 6이므로 \(\gcd(48,18) = 6\)입니다. 계산기로 확인하려면 48과 18의 최대공약수는 6입니다.
최대공약수로 전체 공약수 목록 만들기
\(a\)와 \(b\)의 모든 공약수는 두 수의 최대공약수의 약수이고, 최대공약수의 모든 약수는 공약수입니다. 따라서 최대공약수를 알면 그 약수만 나열하면 됩니다. 최대공약수가 6이면 약수는 1, 2, 3, 6이며, 이는 2단계에서 찾은 공통 약수와 일치합니다. 한 수가 아닌 두 수를 각각 인수분해하는 대신 하나만 인수분해하면 되므로 큰 수에서 훨씬 빠릅니다.
최대공약수가 1이면 두 수는 서로소이며, 공약수는 1뿐입니다.
계산 규칙과 경계 사례
아래 사례는 모두 이 계산기로 실제 계산한 것이며, 결과 열은 계산기가 실제로 돌려준 값입니다.
| 사례 | 입력 | 결과 |
|---|---|---|
| 음수 포함 (−12와 18) | -12, 18 | 1, 2, 3, 6 |
| 0 포함 (0과 12) | 0, 12 | 1, 2, 3, 4, 6, 12 |
2026-11-08 확인
자주 묻는 질문
두 수는 항상 공약수를 가지나요? 네. 모든 양의 정수 쌍은 1이라는 공약수를 공유합니다. 만약 1이 유일한 공약수라면 그 두 수는 서로소(coprime)라고 합니다.
공약수와 최대공약수(GCF)는 어떻게 다른가요? 공약수는 두 수가 공통으로 가지는 모든 약수를 말하고, 최대공약수(GCF)는 그중 가장 큰 하나를 가리킵니다.
음수나 0도 입력할 수 있나요? 이 계산기는 양의 정수를 기준으로 합니다. 음수를 입력하면 절댓값으로 처리하며, 1보다 작은 값은 1로 보정됩니다.