최대공약수 계산기

24 = 2³ × 3, 36 = 2² × 3², 60 = 2² × 3 × 5 ⇒ 최대공약수(24, 36, 60) = 2² × 3 = 12, 그리고 셋의 공약수는 1, 2, 3, 4, 6, 12

24, 36, 60

비교할 수들이며 두 개에서 열 개까지이고, 각각 1에서 1000000 사이의 정수입니다. 공백이나 쉼표, 세미콜론으로 구분하므로 24 36 60과 24, 36, 60은 같은 입력입니다. 소수점이나 분수 막대는 반올림하지 않고 거부하고, 0도 거부합니다. 최대공약수(0, 0)에 대한 단일한 관례가 없고, 이 페이지가 그것을 대신 골라 주지 않기 때문입니다

2³ × 3

24의 소인수분해이며, 2가 세 번과 3이 한 번입니다. 1보다 큰 모든 정수는 이런 분해를 정확히 하나만 갖고, 그래서 두 번째 방법이 성립합니다

2² × 3

세 분해가 모두 동의하는 부분이며, 2가 두 번과 3이 한 번이므로 4 × 3 = 12입니다. 규칙은 공유하는 소수마다 가장 작은 거듭제곱을 택하는 것입니다. 가장 큰 쪽이 아니라 가장 작은 쪽입니다. 이 값은 모든 수를 나눠야 하므로, 가장 인색한 쪽이 허락하는 것보다 클 수 없습니다

1, 2, 3, 4, 6, 12

모든 공약수를 오름차순으로 쓴 것입니다. 마지막이 최대공약수이고, 이 목록이 곧 검산입니다. 12는 24, 36, 60을 나머지 없이 나누고, 그다음으로 큰 약수인 18은 36만 나눕니다

최대공약수(a, b, c) = 최대공약수(최대공약수(a, b), c)

셋 이상을 다루는 방식이며, 둘씩 접어 넣는 것입니다. 별도의 방법이 아니라 두 수짜리 방법을 반복하는 것이고, 그래서 이 페이지는 세 수에 대해서도 어느 짝부터 시작하든 같은 답을 냅니다

서로소

공약수가 1뿐이어서 최대공약수가 1인 짝의 이름입니다. 9와 20은 어느 쪽도 소수가 아닌데도 서로소이고, 이웃한 두 정수는 언제나 서로소입니다

분수를 기약분수로 만드는 것이 일상적인 쓰임입니다. 24/36은 양쪽을 12로 나누면 2/3이 되고, 이 페이지의 모든 분수 도구가 가장 먼저 하는 일이 이 단계입니다. 조리법이나 도면을 가장 작은 정수 비로 줄이는 것도 같은 연산의 옷만 바꾼 것입니다. 24 : 36 : 60으로 적힌 배합은 2 : 3 : 5와 같은 배합이고, 라벨에 들어가는 쪽은 두 번째입니다. 산수 수업에서는 이 값을 직접 묻는데, 인쇄되는 공약수 목록이 곧 풀이 과정입니다. 답을 찍은 것이 아니라 약수를 견주어 찾았다는 것이 보이기 때문입니다. 쓰이는 곳이 둘 더 있습니다. 직사각형을 될 수 있는 한 큰 정사각형 타일로 채우는 일은 최대공약수 문제의 다른 모습이고, 답이 곧 타일 한 변의 길이입니다. 그리고 정수론에서는 두 수가 서로소라는 것이 여러 정리의 조건이 되는데, RSA 암호가 기대는 정리도 그중 하나입니다. 법(modulus)은 지수와 서로소일 때에만 안전합니다. 수가 다루기 어려울 때, 예컨대 1071과 462라면 손으로 분해하는 일이 현실적이지 않아지고 유클리드 호제법이 맡습니다. 이 페이지의 예제가 두 길이 같은 21에 이르는 것을 보여 줍니다. 최대공약수를 구하는 계산기가 필요할 때 이 페이지는 답과 함께 검산용 공약수 목록까지 주고, 답 하나만 필요하면 그 한 줄을 읽으면 됩니다

1. 24, 36, 60의 최대공약수

   1. 24의 약수: 1, 2, 3, 4, 6, 8, 12, 24
   2. 36의 약수: 1, 2, 3, 4, 6, 9, 12, 18, 36
   3. 60의 약수: 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30, 60
   4. 세 목록에 모두 들어 있는 것만 남깁니다: 1, 2, 3, 4, 6, 12
   5. 그중 가장 큰 것이 12이므로 최대공약수는 12입니다

   기본 입력이고, 아래 표가 이 예를 처음부터 끝까지 따라갑니다. 소인수분해로 하면 이렇습니다. 24는 2³ × 3, 36은 2² × 3², 60은 2² × 3 × 5이고, 셋이 함께 갖는 것은 2²와 3 하나라서 2² × 3 = 12입니다. 남겨 둘 만한 것은 공약수 목록입니다. 12가 여러 공약수 중 하나가 아니라 가장 큰 것임을 보여 주는 유일한 출력이기 때문입니다. 8과 9는 각각 셋 중 둘을 나누지만 셋 모두를 나누지는 못합니다.

2. 다루기 어려운 수: 1071과 462

   1. 1071 ÷ 462 = 2 나머지 147
   2. 462 ÷ 147 = 3 나머지 21
   3. 147 ÷ 21 = 7 나머지 0 — 나머지가 0이 되었으므로 멈춥니다
   4. 마지막으로 0이 아닌 나머지가 21이므로 최대공약수는 21입니다
   5. 두 수를 분해해서 검산합니다. 1071 = 3 × 7 × 51이고 462 = 2 × 3 × 7 × 11이므로 공유하는 부분은 3 × 7입니다

   이 짝이 이 페이지에 유클리드 호제법이 있는 이유입니다. 어느 쪽도 한눈에 분해되지 않고, 약수를 손으로 나열하는 일은 느리고 실수하기 쉽습니다. 나눗셈 네 번이면 끝납니다. 답 21은 두 수를 모두 나누는 가장 큰 수이기도 하고, 공약수 목록이 1, 3, 7, 21로 짧다는 점도 눈여겨볼 만합니다. 두 수가 공유하는 것이 적다는 신호는 대개 이렇게 짧은 목록입니다.

3. 서로소인 두 수: 9와 20

   1. 9의 약수: 1, 3, 9
   2. 20의 약수: 1, 2, 4, 5, 10, 20
   3. 두 목록이 함께 갖는 약수는 1뿐입니다
   4. 따라서 최대공약수는 1입니다

   답이 1인 것은 실패가 아니라 진짜 답입니다. 두 수가 서로소인 것입니다. 두 수가 소수를 전혀 공유하지 않을 때마다 일어나고, 흔합니다. 이웃한 두 정수는 언제나 서로소이고, 어떤 소수와 그 소수의 배수가 아닌 수도 그렇습니다. 이 페이지에서 서로소인 짝은 될 수 있는 한 가장 짧은 공약수 목록, 곧 1 하나로 돌아옵니다.

4. 자기 자신과 짝지은 수: 36과 36

   1. 36의 약수: 1, 2, 3, 4, 6, 9, 12, 18, 36
   2. 목록의 두 항목이 같은 수이므로 두 약수 목록은 완전히 같습니다
   3. 함께 갖는 약수 중 가장 큰 것은 36 자신입니다

   답이 오를 수 있는 위쪽 끝입니다. 최대공약수는 목록에서 가장 작은 수보다 클 수 없고, 가장 작은 수가 나머지 모두를 나눌 때 정확히 그 천장에 닿습니다. 입력에 같은 수를 되풀이해도 아무것도 달라지지 않습니다. 36과 36의 최대공약수는 36이고, 이는 수 하나짜리 목록의 최대공약수와 같습니다.

모든 수는 1에서 1000000 사이의 정수여야 하고, 개수는 둘에서 열 사이여야 합니다. 0을 거부하는 것은 빠뜨린 것이 아니라 정한 것입니다. 최대공약수(0, 5)는 한 관례에서는 5이고 다른 관례에서는 정의되지 않으며, 최대공약수(0, 0)는 어떤 교과서에서는 0이고 나머지에서는 아예 정의되지 않습니다. 그중 하나를 인쇄하면 다른 관례를 따르는 독자에게는 틀린 답이 되므로, 이 페이지는 양의 정수를 요청합니다. 음수도 같은 이유로 거부합니다. −24와 36의 최대공약수는 대부분의 교재에서 12이지만, 부호 규칙은 이 페이지가 밝히지 않은 별도의 관례이기 때문입니다. 소수와 분수는 반올림하지 않고 거부합니다. 최대공약수는 정수가 정수를 나눈다는 주장이고, 2.5 ÷ 1.25는 나머지가 없어서 답이 의미를 잃습니다. 구분자는 공백, 쉼표, 세미콜론을 쓸 수 있고 섞어도 됩니다. 그 밖의 문자는 수의 일부로 취급되어 입력을 읽을 수 없게 만듭니다. 아래 참고표는 24, 36, 60에 고정되어 있고 입력한 값을 따라가지 않습니다. 위의 패널이 여러분의 수에 답하고, 표는 방법을 보여 줍니다. 같은 수를 되풀이해 넣어도 되고 결과는 달라지지 않습니다. 답은 근사가 아니라 정확합니다. 이 페이지의 모든 값은 기계가 정확히 담는 범위 안의 정수입니다.

최대공약수를 손으로 어떻게 구하나요?

각 수의 약수를 나열하고 모두가 함께 갖는 것 중 가장 큰 것을 고르면 됩니다. 24, 36, 60이라면 그 목록들이 12에서 만나므로 최대공약수는 12입니다. 수가 클 때 더 빠른 길은 유클리드 호제법입니다. 큰 수를 작은 수로 나누고, 큰 수를 나머지로 바꿔 넣기를 나머지가 0이 될 때까지 반복합니다. 1071과 462라면 나눗셈 네 번이고 답은 21입니다. 두 길은 같은 수에 이르고, 위의 예제가 둘 다 보여 줍니다.

최대공약수가 1로 나오는 것은 무슨 뜻인가요?

그 수들이 서로소라는 뜻이고, 뭔가 잘못되었다는 신호가 아니라 정상적인 답입니다. 9와 20은 소수를 전혀 공유하지 않으므로 둘을 나누는 수는 1뿐입니다. 흔한 일입니다. 이웃한 두 정수는 언제나 서로소이고, 어떤 소수와 그 소수의 배수가 아닌 수도 그렇습니다. 그런 경우 공약수 목록은 1 하나로 돌아옵니다.

0과 음수를 왜 거부하나요?

답이 이 페이지가 밝히지 않은 관례에 달려 있기 때문입니다. 최대공약수(0, 5)는 많은 교과서에서 5이지만 다른 책에서는 정의되지 않고, 최대공약수(0, 0)는 어떤 교재에서는 0이지만 나머지에서는 아예 정의되지 않습니다. 음수는 별도의 부호 규칙을 끌고 옵니다. 관례 하나를 조용히 골라 인쇄하는 대신, 이 페이지는 모든 출처가 동의하는 1 이상의 정수를 요청합니다.

소인수분해로 구하는 방법은 어떻게 되나요?

각 수를 소수로 쪼갠 뒤 모든 수에 나타나는 소수만, 각각 가장 작은 거듭제곱으로 남깁니다. 24, 36, 60이라면 2²와 3이므로 답은 12입니다. 가장 작은 거듭제곱이어야 하는 까닭은 이 값이 목록의 모든 수를 나눠야 하기 때문입니다. 36에는 3²이 있지만 24에는 3이 하나뿐이므로, 3을 두 번 쓰면 24를 나누는 순간 깨집니다. 소인수분해는 다루기 어려운 수에서 유클리드 호제법보다 느리지만, 답이 왜 그 값인지 설명해 줍니다.

답이 목록에서 가장 작은 수보다 클 수 있나요?

없습니다. 목록의 공약수는 그중 가장 작은 수를 나눠야 하므로 그 수를 넘을 수 없고, 가장 작은 수가 나머지 모두를 나눌 때 정확히 그 천장에 닿습니다. 36과 36의 최대공약수는 36이고, 12, 24, 36의 최대공약수는 12입니다. 또한 1보다 작아질 수도 없습니다. 1은 모든 정수를 나누기 때문입니다.

최대공약수는 어디에 쓰나요?

가장 흔한 쓰임은 분수를 기약분수로 만드는 것입니다. 24/36의 양쪽을 12로 나누면 분모가 될 수 있는 한 가장 작은 2/3이 됩니다. 비를 줄이는 것도 같은 단계입니다. 24 : 36 : 60은 2 : 3 : 5와 같은 배합입니다. 그리고 두 수가 서로소라는 것, 곧 최대공약수가 1이라는 것은 정수론의 여러 결과가 필요로 하는 조건이며, RSA 암호가 기대는 정리도 그중 하나입니다.

• Greatest common divisor — 정의, 유클리드 호제법, 그리고 소인수분해로 구하는 방법 — Wolfram MathWorld (United States)
• Divisor — 어떤 정수가 다른 정수를 정확히 나눈다는 것의 뜻, 그리고 약수를 짝으로 나열하는 방식 — Wolfram MathWorld (United States)
• Divisors of n arranged as a triangle — 1; 1, 2; 1, 3; 1, 2, 4; … 로 이어지는 수열이며 아래 표의 약수 열이 여기서 나왔고, OEIS A027750으로 등록되어 있습니다 — OEIS Foundation Inc. (United States)
• 教育部关于印发义务教育课程方案和课程标准(2022年版)的通知 — 이 통지의 첨부 목록 제5항이 《义务教育数学课程标准(2022年版)》에 해당하며, 약수와 배수의 이해, 공약수와 최대공약수는 이 교육과정의 수와 대수 영역 내용이므로 원문과 학년군 요구는 이 첨부를 기준으로 합니다 — 中华人民共和国教育部