유클리드 호제법 최대공약수 계산기

계산 입력

값 1

값 2

결과

https://example.com

최대공약수

4

최대공약수 (GCF, GCD)

Solution — Euclid's Algorithm

Step 1: 2260 ÷ 816 = 2 R 628   (2260 = 2 × 816 + 628)
Step 2: 816 ÷ 628 = 1 R 188   (816 = 1 × 628 + 188)
Step 3: 628 ÷ 188 = 3 R 64   (628 = 3 × 188 + 64)
Step 4: 188 ÷ 64 = 2 R 60   (188 = 2 × 64 + 60)
Step 5: 64 ÷ 60 = 1 R 4   (64 = 1 × 60 + 4)
Step 6: 60 ÷ 4 = 15 R 0   (60 = 15 × 4 + 0)

유클리드 호제법이란?

최대공약수(GCF)는 최대공약수(GCD)라고도 부르며, 두 정수를 모두 나누어떨어지게 하는 가장 큰 자연수를 말합니다. 유클리드 호제법은 나눗셈과 나머지를 반복해 이 값을 구하는 고대의 방법으로, 지금 봐도 놀랄 만큼 효율적입니다. 이 계산기는 임의의 두 자연수에 대한 최대공약수를 알려 주고, 풀이 과정을 따라갈 수 있도록 모든 나눗셈 단계를 함께 보여 줍니다.

유클리드 호제법은 직사각형을 가능한 가장 큰 같은 정사각형으로 채운다 — 그 정사각형의 한 변이 최대공약수다.

사용 방법

값 1과 값 2에 두 자연수를 입력하세요. 계산기는 큰 수를 피제수(나누어지는 수), 작은 수를 제수(나누는 수)로 삼아 나머지가 0이 될 때까지 반복해서 나눕니다. 이때 마지막으로 나온 0이 아닌 제수가 바로 최대공약수입니다. 두 수를 입력하는 순서는 결과에 영향을 주지 않으며, 최대공약수는 크기에만 의존하므로 음의 부호는 무시됩니다.

공식 풀이

각 단계에서 몫과 나머지를 구합니다. \(a = c \times b + R\)이며, 여기서 \(c = \lfloor a / b \rfloor\), \(R = a \bmod b\)입니다. 그런 다음 \(a\) 자리에 \(b\)를, \(b\) 자리에 \(R\)을 넣고 같은 과정을 반복합니다. 나머지는 직전 제수보다 항상 작아지므로, 이 과정은 반드시 끝납니다. \(R = 0\)이 되는 순간의 제수가 정답입니다. 재귀식으로 표현하면 다음과 같습니다.

$$\gcd\!\left(\text{Value 1},\ \text{Value 2}\right) = \gcd\!\left(b,\ a \bmod b\right),\quad \gcd(a, 0) = a$$

광고

예제 풀이

GCF(816, 2260)을 구해 봅시다. \(a = 2260\), \(b = 816\)으로 둡니다.

$$2260 = 2 \times 816 + 628$$ $$816 = 1 \times 628 + 188$$ $$628 = 3 \times 188 + 64$$ $$188 = 2 \times 64 + 60$$ $$64 = 1 \times 60 + 4$$ $$60 = 15 \times 4 + 0$$ 제수가 4일 때 나머지가 0이 되므로, GCF(816, 2260) = 4입니다.

각 단계마다 (a, b)를 (b, a mod b)로 바꿔 나머지가 0이 될 때까지 반복하며, 마지막 0이 아닌 약수가 최대공약수다.

자주 묻는 질문

GCF와 GCD는 같은 건가요? 네. 영어의 "greatest common factor"와 "greatest common divisor"는 모두 우리말로 최대공약수를 뜻하는 같은 개념입니다. 이 계산기는 두 표현 모두에 해당하는 답을 알려 줍니다.

입력값 중 하나가 0이면 어떻게 되나요? 모든 수는 0을 나누어떨어지게 하므로 \(\gcd(a, 0) = a\) 입니다. 다만 두 값이 모두 0이면 최대공약수는 정의되지 않습니다.

세 수의 최대공약수도 구할 수 있나요? 두 개씩 차례로 적용하면 됩니다. \(\gcd(x, y, z) = \gcd(\gcd(x, y), z)\) 와 같이 계산하세요.