» 수학 계산기 » 최대공약수 계산기, 2개 및 3개 이상의 자연수에 대한 최대공약수 계산

최대공약수 계산기, 2개 및 3개 이상의 자연수에 대한 최대공약수 계산

아래 입력 칸에 두 개 이상의 수치를 입력하면, 입력한 수들의 최대공약수를 확인할 수 있습니다.

최대공약수 계산기

목차:

최대공약수 계산기 설명

최대공약수는 2개 이상의 양의 정수(자연수)를 각각 나머지 없이 나눌 수 있는 공약수 중 가장 큰 공약수입니다.

최대공약수 계산기를 이용하려면, 입력 칸에 두 개의 수를 뛰어 쓰기로 ’36 48’과 같이 따옴표 없이 입력하거나, 콤마로 분리하여 ‘36,48’과 같이 (따옴표 없이) 입력하면 됩니다.

계산 결과에서 표시되는 gcd는 최대공약수에 해당하는 영어 greatest common divisor의 약자입니다.

최대공약수 계산기는 3개 이상의 수에 대해서도 최대 공약수를 계산할 수 있습니다. 이 경우 두 수를 입력 했던 것과 같이 예를 들어, ’18 42 64′ 또는 ’18, 42, 64′ 형식으로 따옴표 없이 입력하면 됩니다.

최대공약수란?

최대공약수는 공약수 중 가장 큰 공약수입니다. 예를 들어, 18과 42라는 두 수의 최대공약수는 두 수의 공통된 약수(공약수) 중 가장 큰 수 입니다.

최대공약수 구하는 법은 잠시 후 설명하니, 여기서는 18과 42의 공약수는 1, 2, 3, 6 네 가지가 있다는 것을 이미 알고 있다고 가정하겠습니다. 최대 공약수는 공약수 중 가장 큰 수 이므로 18과 42의 최대공약수는 6임을 알 수 있습니다.

최대공약수는 영어로는 greatest common factor(gcf)라고 하기도 하고, highest common factor(hcf) 또는 greatest common divisor(gcd)라고 하기도 합니다. 3가지 용어 중 gcd 또는 gcf를 주로 씁니다.

어떤 두 수, a 와 b의 최대공약수를 영어 약수를 이용하여 gcd(a, b)라고 표시합니다. ‘a와 b의 최대공약수’라는 의미입니다. gcf(a, b) 또는 hcf(a, b)도 같은 의미입니다.

최대 공약수는 어떻게 활용될까?

가장 먼저 생각할 수 있는 것은 분수를 약분할 때 최대공약수를 이용하면 기약분수로 빠르게 약분할 수 있다는 것입니다.

기약분수는 분모와 분자가 1 이외에는 공통된 약수가 없는 상태의 분수인데요, 보통은 분모와 분자의 공약수로 약분하는 과정을 거쳐 기약분수를 만들지만, 최대공약수로 약분하면 한번에 기약분수를 만들 수 있게 됩니다.

1842를 기약분수로 만들려면 두 수의 최대공약수인 6으로 분모와 분자를 약분하면 됩니다. 분모와 분자를 6으로 나누면 37이라는 기약분수가 됩니다.

실제 생활에서 최대공약수과 활용되는 영역은 예를 들어, 가로 42㎡ × 세로 18㎡ 인 땅이 있는데 이 땅을 잘게 쪼개 작은 정사각형 모양으로 나누고자 할 때 가장 큰 정사각형으로 나눌 수 있는 방법을 찾는 것입니다.

직사각형 모양의 땅을 작은 정사각형으로 나눌 때 가장 쉽게 생각할 수 있는 정사각형은 가로 세로 길이가 1㎡인 정사각형입니다. 이 경우 가로로는 42개의 정사각형 모양으로 나누어 지고, 세로는 18개의 정사각형으로 나누어 질 것입니다.

1㎡ 보다 큰 정사각형은 42와 18를 동시에 나눌 수 있는 가로 세로가 6㎡인 정사각형을 생각할 수 있습니다. 이 경우에는 가로로 7개, 세로로 3개의 정사각형으로 나누어 집니다.

이런 식으로 해서 42㎡와 18㎡의 직사각형 땅을 정사각형으로 나눌 때 가장 큰 정사각형은 42㎡와 18㎡의 최대공약수인 가로 세로 6㎡의 정사각형임을 알 수 있습니다.

직사각형을 작은 정사각형으로 분할할 때의 가장 큰 정사각형

최대 공약수 구하는 법

어떤 두 수의 최대공약수를 계산하는 법은 5가지가 있습니다.

1. 약수 중 공약수, 공약수 중 최대 공약수

최대 공약수를 찾는 가장 기본적인 방법입니다. 18과 42의 최대공약수를 구하는 법을 예로 들면,

  • 18의 약수를 나열합니다: 1, 2, 3, 6, 9, 18
  • 42의 약수를 구합니다: 1, 2, 3, 6, 7, 14, 21, 42
  • 18과 42에 공통된 약수를 찾습니다: 1, 2, 3, 6
  • 공통된 수 중 가장 큰 수가 최대공약수입니다. 즉, 공약수 1, 2, 3, 6 중 가장 공약수인 6이 최대 공약수

이 방법은 최대공약수의 개념에 가장 잘 부합하는 방법이지만, 약수의 개수가 많은 경우에는 번거로운 방법입니다. 그래서 보통은 두 번째 방법을 이용하는 경우가 많습니다.

2. 두 수를 동시에 나눌 수 있는 소수에서 출발하는 법

이 방법은 두 수를 동시에 나누어 떨어지게 할 수 있는 소수로부터 출발하여 최대공약수를 찾는 방법인데요, 아래 이미지에서 볼 수 있는 것과 같은 단계로 최대공약수를 계산하게 됩니다.

  • 1단계: 두 수를 동시에 나누어 떨어지게 할 수 있는 소수로 두 수를 나누어 각각의 몫을 기록,
  • 2단계: 1단계에서 계산한 두 개의 몫을 동시에 나눌 수 있는 소수로 다시 나누고 몫을 기록,

2단계를 두 개의 몫을 나누어 떨어지게 하는 수가 1 이외에는 없을 때까지 반복합니다. 마지막 단계에 도달하면 소수 부분에 있는 수를 모두 곱하여 최대 공약수를 구할 수 있게 됩니다. 글로 설명한 내용이 이해가 안된다면 아래에 있는 이미지를 참고하시면 이해할 수 있을 것입니다.

나눗셈으로 최대 공약수 구하는 법

18과 42처럼 2단계를 끝으로 계산 과정이 끝날 수도 있고, 3단계 이상으로 나갈 수도 있습니다.

어쨌든 전(前) 단계에서 계산한 몫을 나누어 떨어지게 할 수 있는 수가 1 이외는 없을 때까지 2단계를 반복한 후 가장 왼쪽 (소수 부분)에 있는 수를 모두 곱하면 최대 공약수가 된다는 점을 기억하면 됩니다.

3. 소인수분해를 이용하는 법

두 번째와 같은 나눗셈을 이용하는 법은 초등 수학 수준에서 최대공약수를 구하는 법입니다. 소인수분해를 이용하는 방법은 중등 수학에서 배우게 됩니다.

이 방법은 두 수를 각각 소인수분해한 후 두 수에 공통으로 들어가는 인수 중 지수가 낮을 것을 골라 곱하여 최대공약수를 구하게 됩니다. 18과 42의 두 수를 예로 들면,

  • 18을 소인수분해하면 2×32,
  • 42를 소인수분해하면 2×3×7
  • 18과 42에 공통으로 들어가는 인수는 2와 3이므로,

18과 42의 최대공약수는 2×3인 6.

18과 42의 공통 인수인 2와 3에서 3이 32이 아니라 3임에 주의해야 합니다.

이는 어떤 수에는 3이 개 들어가고 다른 어떤 수에는 3이 개가 들어간다면 공통으로는 3이 개 들어가는 것이라고 보아야 하기 때문입니다. 이처럼 공통 인수의 지수가 서로 다르다면 낮은 지수의 인수를 골라야 합니다.

이 원칙에 따라, 예를 들어, 어떤 수를 소인수분해 했더니 23×32×74이고, 다른 어떤 수를 소인수분해하면 25×5 2×72×11 라면, 최대공약수는 23×72 입니다.

4. 최소공배수를 이용하는 법

최소공배수는 어떤 두 수의 공통된 배수중 가장 작은 수인데요, 만약 어떤 두 수의 최소공배수를 알고 있다면, 다음의 공식을 이용하여 최대공약수를 계산할 수 있습니다. 어떤 두 수를 각각 a, b라 하면,

$$ \text{최대공약수} = \frac{a \times b}{\text{최소공배수}} $$

최대공약수: gcd, 최소공배수: lcm 이라는 기호를 쓰면 위 공식은 다음과 같이 표시할 수 있습니다.

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

18과 42의 최소공배수는 126입니다. 이를 이용하여 두 수의 최대 공약수를 구하면 다음과 같습니다.

$$ \frac{18 \times 42}{126} = 6 $$

5. 유클리드 알고리즘을 이용하는 법

유클리드 알고리듬(Euclid’s Algorithm)를 이용하는 법은 직접 손으로 최대공약수를 계산하는 경우 보다는 최대공약수를 구하는 프로그래밍을 할 때 주로 이용됩니다.

어떤 두 수 a, b 에서 a가 b보다 더 큰 경우(어느 수가 더 큰 지는 중요하지 않습니다.), a를 b로 나누어 떨어지면 b가 최대 공약수.

만약, 나누어 떨어지지 않는다면,

  • 1단계: a ÷ b 를 몫과 나머지 형식으로 표시. 몫을 q라 하고 나머지를 b1 이라 하면, a = (b×q)+b1,
  • 2단계: b를 b1를 나누고 몫과 나머지 형식으로 표시. 이때의 몫을 q1, 나머지를 b2라고 하면, b ÷ b1 = (b1×q1)+b2,
  • 2단계에서 b2가 영(0)라면, 즉, b를 b1으로 나누어 떨어지면, b1이 최대공약수, 나머지(b2)가 0이 아니라면, 2단계에서 한 방법을 반복,
  • 3단계: b1을 b2로 나누고 이때의 몫을 q2, 나머지를 b3이라 하면, b1 ÷ b2 = (b2×q)+b3,

나머지가 0이 될 때까지 위 과정을 반복하고, 나머지가 0일 때의 나누는 수를 찾으면 그 수가 최대공약수입니다.

18과 42를 예로 들어 유클리드 알고리즘으로 최대 공약수를 구하면,

  • 42 ÷ 18 = (18×2)+6
  • 18 ÷ 6 = (6×3)+0
  • 나머지가 0이므로 이 때의 나누는 수 6이 두 수의 최대 공약수.

3개 이상의 수에 대한 최대공약수 구하는 법

지금까지는 어떤 두 수의 최대공약수를 계산하는 법에 대해 알아 보았는데요, 마지막으로 한 가지 더 알고 있으면 좋은 내용이 있습니다.

2개의 수가 아니라 3개의 수에 대한 최대공약수는 어떻게 구할까요?

두 수를 묶어서 최대공약수를 계산 한 후, 이 최대공약수와 남은 수의 최대 공약수를 구하면 됩니다. 예를 들어, 18, 42, 64 라는 세 가지 수의 최대공약수를 구하려면,

  • 18과 42의 최대공약수를 구합니다. 답: 6
  • 6과 64의 최대공약수를 구합니다. 답: 2

따라서, gcd(18, 42, 64) = 2.

먼저 두 수를 묶어서 최대공약수를 구한 후 이 수와 남은 수와의 최대공약수를 구하면 되므로 어떤 두 수를 묶는지는 중요하지 않습니다. 즉 18과 42의 최대공약수가 아니라 42와 64의 최대공약수를 구한 후 이 최대공약수와 18의 최대공약수를 구해도 답은 동일합니다.