공약수 및 최대공약수(GCF) 계산기

공약수 및 최대공약수(GCF) 계산기

성장 중 AI Skill PRO

계산 입력

자연수를 쉼표로 구분해 입력하세요

공식

gcd⁡(수 n1,n2,…,nk)=g여기서{g=gcd⁡(gcd⁡(n1,n2),…,nk)gcd⁡(a,b)=gcd⁡(b,amodb),gcd⁡(a,0)=a공약수={d∈ℤ+:gmodd=0}\begin{gathered} \gcd\left({{\text{수 } n_1, n_2, \dots, n_k}}\right) = g \\[1.5em] \text{여기서}\quad \left\{ \begin{aligned} g &= \gcd\left(\gcd(n_1, n_2), \dots, n_k\right) \\ \gcd(a,b) &= \gcd(b,\; a \bmod b), \quad \gcd(a,0) = a \\ \text{공약수} &= \{\, d \in \mathbb{Z}^{+} : g \bmod d = 0 \,\} \end{aligned} \right. \end{gathered}
계산 단계 보기 (1)
  1. 각 수의 약수

    F(n)={d∈ℤ+:nmodd=0}=⋃i=1⌊n⌋{i,ni}nmodi=0,n∈수F(n) = \{\, d \in \mathbb{Z}^{+} : n \bmod d = 0 \,\} = \bigcup_{i=1}^{\left\lfloor \sqrt{n} \right\rfloor} \left\{ i,\; \tfrac{n}{i} \right\}_{\, n \bmod i = 0}, \quad n \in \text{수}

    입력한 각 수에 대해 i를 제곱근까지 시험하고 i와 n÷i를 짝지어 모든 양의 약수를 나열합니다.

사용 통계

광고

결과

최대공약수
8
GCF (최대공약수, GCD)
약수: 16 1, 2, 4, 8, 16
약수: 24 1, 2, 3, 4, 6, 8, 12, 24
약수: 64 1, 2, 4, 8, 16, 32, 64
약수: 136 1, 2, 4, 8, 17, 34, 68, 136
공약수는 다음과 같습니다: 1, 2, 4, 8

이 페이지의 오류 신고

이 계산기는 무엇을 하나요?

두 개 이상의 양의 정수를 입력하면 세 가지 결과를 한꺼번에 보여 줍니다. 각 수의 약수(나누어떨어지게 하는 수) 전체 목록, 모든 수가 공통으로 가지는 공약수, 그리고 최대공약수(GCF, 영어로는 GCD라고도 함)입니다. 분수를 약분하거나 식을 인수분해할 때, 또는 정수론 숙제를 풀 때 유용합니다.

두 수의 약수를 나타내는 겹친 두 원으로, 공통 약수가 가운데에 있음
공약수는 모든 수가 공유하는 약수이며, 그중 가장 큰 것이 최대공약수(GCD)입니다.

사용 방법

자연수를 쉼표로 구분해 입력하세요. 예를 들어 136, 64, 24, 16처럼 적으면 됩니다. 그러면 각 수의 약수 목록이 오름차순으로 표시되고, 이어서 공약수와 최대공약수(GCF) 값이 나타납니다. 입력값은 반드시 양의 정수여야 하며, 0이나 음수, 소수는 약수를 구하는 데 사용할 수 없습니다.

계산 원리

정수 d가 n의 약수라는 것은 \(n \bmod d = 0\), 즉 나머지 없이 나누어떨어진다는 뜻입니다. 모든 약수를 빠르게 찾으려면 i를 1부터 n의 제곱근까지 차례로 확인합니다. i가 n을 나누어떨어지게 하면 \(i\)와 \(n/i\) 둘 다 약수가 됩니다. 여러 수의 최대공약수는 유클리드 호제법을 두 수씩 적용해 구합니다. b가 0이 아닌 동안 (a, b)를 (b, a mod b)로 계속 바꿔 가다가, 마지막에 남는 a가 바로 최대공약수입니다. $$\gcd(a, 0) = a, \quad \gcd(a, b) = \gcd(b, \; a \bmod b)$$ 한 가지 알아 두면 좋은 사실은, 전체 수들의 공약수는 곧 최대공약수의 약수와 정확히 같다는 점입니다. $$\text{CommonFactors} = \{\, d : g \bmod d = 0 \,\}, \quad g = \gcd(n_1, n_2, \dots)$$

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

예제 풀이

136, 64, 24, 16의 경우를 봅시다. 16의 약수는 1, 2, 4, 8, 16이고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24, 64의 약수는 1, 2, 4, 8, 16, 32, 64, 136의 약수는 1, 2, 4, 8, 17, 34, 68, 136입니다. 유클리드 호제법을 적용하면 \(\gcd(16, 24) = 8\), 다시 \(\gcd(8, 64) = 8\), \(\gcd(8, 136) = 8\)이 되어 최대공약수는 8입니다. 8의 약수는 1, 2, 4, 8이며, 바로 이 값들이 공약수가 됩니다.

유형별 숫자 집합의 최대공약수(GCF) 결과

최대공약수(GCF)는 숫자들이 서로 어떤 관계에 있는지에 따라 달라집니다. 표에는 몇 가지 대표적인 경우가 나와 있습니다. 어떤 집합의 공약수는 정확히 그 집합의 최대공약수의 약수들입니다.

숫자 GCF 공약수 관계 유형
8과 15 1 1 서로소 (1 외에 공통 약수가 없음)
12와 36 12 1, 2, 3, 4, 6, 12 배수 관계 (36은 12의 배수)
18, 24, 30 6 1, 2, 3, 6 공통 약수를 가진 세 수
17과 31 1 1 서로 다른 두 소수 (항상 서로소)
20과 20 20 1, 2, 4, 5, 10, 20 같은 수 (GCF는 그 수 자체)
48과 180 12 1, 2, 3, 4, 6, 12 소인수가 일부만 겹침

48과 180 확인: \(48 = 2^4 \cdot 3\)이고 \(180 = 2^2 \cdot 3^2 \cdot 5\)입니다. 공통 소수 각각의 가장 낮은 거듭제곱을 취하면 \(2^2 \cdot 3 = 12\)입니다.

GCF가 알려 주는 것과 활용 분야

  • GCF = 1은 서로소를 뜻합니다. 두 수는 공통 소인수가 없습니다. 두 수 자체가 소수일 필요는 없으며, 8과 15는 둘 다 소수가 아니지만 서로소입니다.
  • GCF는 가장 작은 수와 같습니다. 그 가장 작은 수는 나머지 모든 수의 약수입니다. 예를 들어 \(\gcd(12, 36) = 12\)입니다.
  • 분수 약분. 분자와 분모를 그들의 GCF로 나누면 한 번에 기약분수가 됩니다. \(\gcd(24, 36) = 12\)이므로 \(\frac{24}{36} = \frac{24 \div 12}{36 \div 12} = \frac{2}{3}\)입니다.
  • 가장 많은 동일 묶음. 펜 24개와 연필 36개가 있고 모든 물건을 남김없이 사용해 같은 묶음을 만들고 싶다면, 만들 수 있는 묶음의 최대 개수는 \(\gcd(24, 36) = 12\)입니다. 각 묶음에는 펜 2개와 연필 3개가 들어갑니다.
  • 정사각형 타일. 48 cm × 180 cm 면적을 자르지 않고 정확히 채우는 가장 큰 정사각형 타일의 한 변은 \(\gcd(48, 180) = 12\) cm입니다. 즉 가로 4개, 세로 15개의 타일이 필요합니다.
  • 최소공배수(LCM)와의 관계. 두 양의 정수에 대해 \(\gcd(a,b) \cdot \operatorname{lcm}(a,b) = a \cdot b\)가 성립합니다. 예: \(\gcd(12, 18) = 6\)이고 \(\operatorname{lcm}(12, 18) = 36\)이므로 \(6 \cdot 36 = 216 = 12 \cdot 18\)입니다. 이 항등식은 세 개 이상의 수가 아니라 두 수에만 적용됩니다.
광고

핵심 용어: 인수, 약수, GCF, 서로소

인수 (약수)
어떤 수를 나머지 없이 나누는 양의 정수입니다. 12의 인수는 1, 2, 3, 4, 6, 12입니다.
배수
어떤 수와 임의의 정수의 곱입니다. 4의 배수에는 4, 8, 12, 16 등이 있습니다. \(d\)가 \(n\)의 인수이면 \(n\)은 \(d\)의 배수입니다.
공약수
집합에 속한 모든 수의 인수인 수입니다. 12와 18의 공약수는 1, 2, 3, 6입니다.
GCF / GCD / HCF
최대공약수로, 최대공약수(greatest common divisor) 또는 최고공약수(highest common factor)라고도 합니다. 공약수들 중 가장 큰 수입니다. 세 이름은 모두 같은 뜻입니다.
서로소 (상대적 소수)
공통 인수가 1뿐인 수들이며, 따라서 이들의 GCF는 1입니다.
소수
1보다 큰 정수로, 양의 인수가 1과 자기 자신뿐인 수입니다. 예: 2, 3, 5, 7, 11, 17, 31.
유클리드 호제법
나머지가 0이 될 때까지 쌍 \((a, b)\)을 \((b,\; a \bmod b)\)로 반복해서 바꾸는 방법입니다. 마지막으로 0이 아닌 값이 GCF입니다. 예: \(\gcd(180, 48)\): \(180 = 3 \cdot 48 + 36\), 다음 \(48 = 1 \cdot 36 + 12\), 다음 \(36 = 3 \cdot 12 + 0\)이므로 GCF는 12입니다. 세 개 이상의 수에는 단계적으로 적용합니다: \(\gcd(\gcd(n_1, n_2), n_3)\).

자주 묻는 질문

GCF와 GCD는 같은 건가요? 네, 같습니다. 영어의 "greatest common factor(최대공약수)"와 "greatest common divisor"는 같은 값을 가리키는 두 가지 이름일 뿐입니다.

공통 약수가 하나도 없으면 어떻게 되나요? 모든 양의 정수는 1을 공통 약수로 가지므로, 공약수는 최소한 {1}이고 최대공약수도 최소 1입니다. 공통 약수가 1뿐인 수들을 서로소(coprime)라고 합니다.

숫자를 하나만 입력해도 되나요? 네. 그 수의 약수가 나열되고, 최대공약수는 그 수 자신이 됩니다.

최종 업데이트:

수학 및 통계 인기 계산기

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