최대공약수를 구할 정수를 쉼표(,)로 구분해 2개 이상 입력해 주세요. 3개 이상도 한 번에 계산할 수 있으며, 각 수의 소인수분해와 공통 소인수도 보여 줍니다.
이 페이지에서 할 수 있는 것
- 쉼표로 구분해 정수를 넣기만 하면 최대공약수(영어로는 GCD 또는 GCF)를 바로 알 수 있습니다
- 2개뿐 아니라 ‘16, 88, 104’처럼 3개 이상인 정수의 최대공약수도 한 번에 계산할 수 있습니다
- 각 정수의 소인수분해와 공통 소인수도 함께 보여 주므로, 답을 구하는 법과 확인하는 법까지 배울 수 있습니다
- 공식의 쉬운 해설과 Excel, Google 스프레드시트, Python에 바로 복사해 쓸 수 있는 수식도 이 페이지에 모아 두었습니다
이 계산은 어디에 쓰일까요?
\(\frac{12}{18}\)를 약분할 때 분자와 분모를 최대공약수인 6으로 나누면 한 번에 \(\frac{2}{3}\)가 됩니다.
2로 나누고 다시 3으로 나누는 식으로 여러 번 나누지 않아도, 최대공약수를 쓰면 한 번에 기약분수가 됩니다. 초등학교 수학부터 실무까지 최대공약수가 가장 많이 쓰이는 곳입니다.
과자 24개와 주스 36개를 남김없이 똑같이 나누어 최대한 많은 봉지를 만들고 싶을 때, 만들 수 있는 봉지는 최대 \(\gcd(24, 36) = 12\)봉지이고 한 봉지에 과자 2개, 주스 3개씩 들어갑니다.
학교 행사의 간식 꾸러미나 같은 구성의 준비물 세트를 만들 때처럼, 종류가 다른 물건을 똑같이 나누는 대표적인 계산입니다.
세로 330 cm, 가로 450 cm인 바닥에 정사각형 타일을 틈도 자투리도 없이 깔고 싶을 때, 쓸 수 있는 가장 큰 타일은 \(\gcd(330, 450) = 30\), 즉 한 변이 30 cm인 타일입니다(세로 11장 × 가로 15장).
직사각형을 가장 큰 정사각형으로 나누는 이 계산은 바닥이나 벽 시공, 큰 종이에서 같은 크기의 카드를 낭비 없이 잘라 낼 때 등에 쓰입니다.
맞물리는 두 톱니바퀴의 톱니 수의 최대공약수가 크면 같은 톱니끼리 자주 부딪쳐 한쪽만 닳기 쉽습니다. 그래서 기계 설계에서는 톱니 수를 되도록 서로소(최대공약수가 1)에 가깝게 하는 것이 기본입니다.
자동차나 시계 속 톱니바퀴에도 이렇게 최대공약수를 작게 하는 생각이 쓰이고 있습니다.
온라인 쇼핑이나 인터넷 뱅킹에 쓰이는 RSA 암호는 키를 만들 때 두 수가 서로소인지 확인해야 하는데, 이때 유클리드 호제법이 쓰입니다.
2,000년도 더 전에 만들어진 최대공약수 계산법이 지금은 전 세계의 통신을 지키고 있습니다. 수학의 수명이 얼마나 긴지 보여 주는 예입니다.
공식
용어·기호 해설
기호
| \(\gcd(a, b)\) | 지시디 에이 비 | \(a\)와 \(b\)의 최대공약수를 나타내는 기호입니다. 영어 greatest common divisor(GCD)의 머리글자입니다. greatest common factor(GCF)라고도 하며 \(\mathrm{GCF}(a, b)\)로 쓰기도 하지만 뜻은 완전히 같습니다. |
| \(a \bmod b\) | 에이 모드 비 | \(a\)를 \(b\)로 나눈 나머지입니다. (예: 48 ÷ 18 = 2 … 12이므로 \(48 \bmod 18 = 12\)입니다) |
| \(\mathrm{lcm}(a, b)\) | 엘시엠 에이 비 | \(a\)와 \(b\)의 최소공배수를 나타내는 기호입니다. 영어 least common multiple의 머리글자입니다. (예: \(\mathrm{lcm}(12, 18) = 36\)) |
| \(p_1, p_2, \ldots\) | 피 일, 피 이, … | 공통 소인수를 차례로 늘어놓은 것입니다. 오른쪽 아래의 작은 숫자(첨자)는 ‘첫째, 둘째, …’라는 순서를 나타낼 뿐 계산에는 쓰지 않습니다. |
| \(\cdots\) | 줄임표 | ‘같은 규칙으로 계속 이어진다’는 것을 나타내는 생략 기호입니다. 소인수가 몇 개 있든 같은 방법으로 곱한다는 뜻으로 썼습니다. |
용어
| 약수 | 어떤 정수를 나누어떨어지게 하는 자연수입니다. 12의 약수는 1, 2, 3, 4, 6, 12의 6개입니다. |
| 공약수 | 2개 이상의 정수에 공통인 약수입니다. 12와 18의 공약수는 1, 2, 3, 6입니다. 공약수는 반드시 최대공약수(이 예에서는 6)의 약수입니다. |
| 최대공약수 | 공약수 중에서 가장 큰 수입니다. 초등학교 5학년에 배우며, 영어로는 GCD(greatest common divisor) 또는 GCF(greatest common factor)라고 합니다. |
| 소수 | 1과 자기 자신 외에는 약수가 없는 2 이상의 정수입니다(0.5 같은 ‘소수점이 있는 수’와는 다른 말입니다). 2, 3, 5, 7, 11, 13, …으로 이어집니다. 1은 소수가 아닙니다. |
| 소인수분해 | 정수를 소수만의 곱으로 나타내는 것입니다. (예: \(12 = 2 \times 2 \times 3\)) 이때 쓰인 하나하나의 소수를 소인수라고 합니다. |
| 서로소 | 두 정수의 최대공약수가 1인 것(공약수가 1뿐인 것)을 말합니다. 17과 13처럼 공통 소인수가 하나도 없는 관계입니다. |
| 유클리드 호제법 | ‘큰 수를 작은 수로 나누고, 두 수의 쌍을 작은 수와 나머지로 바꾼다’를 되풀이해 최대공약수를 구하는 방법입니다. 정수론과 컴퓨터 과학의 기본 알고리즘으로, 기원전부터 알려져 ‘세계에서 가장 오래된 알고리즘’이라고도 불립니다. |
| 최소공배수 | 2개 이상의 정수에 공통인 배수 중에서 가장 작은 자연수입니다. 분수의 통분에 씁니다. 두 수에서는 \(\gcd(a, b) \times \mathrm{lcm}(a, b) = a \times b\)의 관계가 있습니다. |
먼저 알아 두면 좋은 내용
이 페이지의 계산을 ‘의미를 알고’ 쓸 수 있도록, 먼저 알아 두면 좋은 내용을 정리했습니다.
막히면 이 표의 내용으로 돌아가 복습하는 것이 지름길입니다.
| 곱셈구구와 나머지가 있는 나눗셈(초등학교 2~3학년, 7~9세) |
|
| 약수와 공약수(초등학교 5학년, 10~11세) |
|
| 분수의 약분(초등학교 5학년, 10~11세) |
|
| 소수와 소인수분해(중학교 1학년, 12~13세) |
|
Excel로 계산하는 방법
| 첫 번째 정수 a | 12 |
| 두 번째 정수 b | 18 |
| 최대공약수 gcd(a, b) | =GCD(B1,B2) |
| 정수 1 | 16 |
| 정수 2 | 88 |
| 정수 3 | 104 |
| 최대공약수 | =GCD(B1:B3) |
| 큰 수 a | 48 |
| 작은 수 b | 18 |
| a를 b로 나눈 나머지(a mod b) | =MOD(B1,B2) |
| gcd(a, b) | =GCD(B1,B2) |
| gcd(b, 나머지)(위와 같습니다) | =GCD(B2,B3) |
| 첫 번째 정수 a | 12 |
| 두 번째 정수 b | 18 |
| 최대공약수 gcd(a, b) | =GCD(B1,B2) |
| 최소공배수 lcm(a, b) | =LCM(B1,B2) |
| gcd × lcm | =B3*B4 |
| a × b(위와 같습니다) | =B1*B2 |
두 번째 표의 ‘=GCD(B1:B3)’처럼 범위를 지정하면 3개 이상인 수의 최대공약수도 한 번에 구할 수 있습니다(B4에 8이 표시됩니다).
세 번째 표는 유클리드 호제법을 확인하는 표입니다. 나머지를 구하는 MOD 함수를 써서 gcd(a, b)와 gcd(b, 나머지)가 같은 값(둘 다 6)이 되는 것을 확인할 수 있습니다.
네 번째 표에서는 gcd × lcm과 a × b가 모두 216이 되어 최소공배수와의 관계를 확인할 수 있습니다. 입력값의 숫자만 바꾸면 그대로 쓸 수 있습니다.
Google 스프레드시트로 계산하는 방법
| 첫 번째 정수 a | 12 |
| 두 번째 정수 b | 18 |
| 최대공약수 gcd(a, b) | =GCD(B1,B2) |
| 정수 1 | 16 |
| 정수 2 | 88 |
| 정수 3 | 104 |
| 최대공약수 | =GCD(B1:B3) |
| 큰 수 a | 48 |
| 작은 수 b | 18 |
| a를 b로 나눈 나머지(a mod b) | =MOD(B1,B2) |
| gcd(a, b) | =GCD(B1,B2) |
| gcd(b, 나머지)(위와 같습니다) | =GCD(B2,B3) |
| 첫 번째 정수 a | 12 |
| 두 번째 정수 b | 18 |
| 최대공약수 gcd(a, b) | =GCD(B1,B2) |
| 최소공배수 lcm(a, b) | =LCM(B1,B2) |
| gcd × lcm | =B3*B4 |
| a × b(위와 같습니다) | =B1*B2 |
표를 통째로 복사해 A1 셀에 붙여 넣고, 입력값의 숫자만 바꾸어 쓰세요.
Python으로 계산하는 방법
from math import gcd
from functools import reduce
numbers = [330, 75, 450, 225] # 최대공약수를 구할 정수(몇 개든 가능)
greatest_common_divisor = reduce(gcd, numbers) # 앞에서부터 2개씩 차례로 gcd를 적용
print(f"{numbers}의 최대공약수: {greatest_common_divisor}")
LaTeX 등 수식 언어로 쓰는 법(복사 가능)
gcd(a, b) = p₁ × p₂ × ⋯
\gcd(a, b) = p_1 \times p_2 \times \cdots
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mi>gcd</mi>
<mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
<mo>=</mo>
<msub><mi>p</mi><mn>1</mn></msub>
<mo>×</mo>
<msub><mi>p</mi><mn>2</mn></msub>
<mo>×</mo>
<mo>⋯</mo>
</mrow>
</math>
gcd(a, b) = p_1 xx p_2 xx cdots
GCD[a, b]
igcd(a, b);
g = gcd(a, b);
gcd(a, b) = p_1 × p_2 × ⋯
gcd(a, b) = gcd(b, a mod b)
\gcd(a, b) = \gcd(b,\ a \bmod b)
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mi>gcd</mi>
<mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
<mo>=</mo>
<mi>gcd</mi>
<mo>(</mo><mi>b</mi><mo>,</mo>
<mi>a</mi><mspace width="0.3em"/><mi>mod</mi><mspace width="0.3em"/><mi>b</mi>
<mo>)</mo>
</mrow>
</math>
gcd(a, b) = gcd(b, a mod b)
GCD[a, b] == GCD[b, Mod[a, b]]
igcd(a, b) = igcd(b, a mod b);
gcd(a, b) == gcd(b, mod(a, b))
gcd(a, b) = gcd(b, a mod b)
gcd(a, b, c) = gcd(gcd(a, b), c)
\gcd(a, b, c) = \gcd(\gcd(a, b),\ c)
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mi>gcd</mi>
<mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo>)</mo>
<mo>=</mo>
<mi>gcd</mi>
<mo>(</mo>
<mi>gcd</mi>
<mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
<mo>,</mo><mi>c</mi>
<mo>)</mo>
</mrow>
</math>
gcd(a, b, c) = gcd(gcd(a, b), c)
GCD[a, b, c]
igcd(igcd(a, b), c);
g = gcd(gcd(a, b), c);
gcd(a, b, c) = gcd(gcd(a, b), c)
gcd(a, b) × lcm(a, b) = a × b
\gcd(a, b) \times \mathrm{lcm}(a, b) = a \times b
<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
<mrow>
<mi>gcd</mi>
<mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
<mo>×</mo>
<mi>lcm</mi>
<mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
<mo>=</mo>
<mi>a</mi>
<mo>×</mo>
<mi>b</mi>
</mrow>
</math>
gcd(a, b) xx lcm(a, b) = a xx b
GCD[a, b]*LCM[a, b] == a*b
igcd(a, b)*ilcm(a, b) = a*b;
gcd(a, b)*lcm(a, b) == a*b
gcd(a, b) × lcm(a, b) = a × b
ChatGPT 에게 물어서 계산하는 방법
당신은 정수 계산 도우미입니다. 다음 계산을 실제로 Python 코드를 실행해서 하고, 실행 결과의 수치만을 근거로 답해 주세요(암산이나 추측으로 답하지 마세요). 정수 330, 75, 450, 225의 4개에 대해 다음을 각각 구해 주세요. 1. 4개 수의 최대공약수 2. 각 수의 소인수분해 3. 4개 수 모두에 공통인 소인수 사용한 식과 실행 결과의 수치를 함께 보여 주세요.
사용법
-
1숫자 입력계산하고 싶은 숫자를 입력란에 입력합니다
-
2계산‘계산’ 버튼을 누릅니다
-
3결과 확인계산 결과가 바로 표시됩니다. 계산의 원리와 공식 해설도 같은 페이지에서 확인할 수 있습니다
DataChef의 특징
전문 지식 없이도 직관적이고 간단하게 사용
개인정보를 등록하지 않고도 이용할 수 있습니다
"다운로드"를 누르면 파일이 자동으로 삭제됩니다
출처 표기 불필요
상업적 이용 허가 연락도 필요 없습니다