기초수학최대공약수#150

최대공약수

Greatest Common Divisor

최대공약수는 두 자연수의 공통인 약수 중 가장 큰 수다. 18과 24를 소인수분해해 최대공약수 6을 구하고, 작은 지수를 택하는 이유, 공통인 소인수로 나누는 방법, 세 수의 최대공약수, 공약수 전체와 서로소를 이해한다.

읽는 시간
약 7분
선수 개념
소인수분해

직관 — 두 상자에서 똑같이 꺼낼 수 있는 묶음

직관

서로 다른 부품이 든 두 상자에서 같은 부품 묶음을 꺼낸다고 생각하자. 어느 한 상자에 없는 부품은 묶음에 넣을 수 없다. 같은 종류의 부품도 두 상자 모두에 있는 개수까지만 고를 수 있다.

소인수분해에서 자연수를 소수들의 곱으로 나타냈다. 여기서는 곱해진 소수 하나하나를 부품으로 본다. 공통으로 고를 수 있는 소인수를 빠짐없이 곱하면 최대공약수가 된다.

초등학교에서 약수를 나열해 찾던 방법을 소인수분해로 바꾸어 보자. 공약수가 무엇인지와 왜 작은 지수를 고르는지 연결하면, 수가 커져도 모든 약수를 먼저 나열할 필요가 없다.

최대공약수는 공통인 약수 중 가장 큰 수다

최대공약수는 두 자연수의 공통인 약수 중 가장 큰 수다. 두 수 모두를 나누어떨어지게 하는 자연수를 공약수라고 한다. 이 글의 자연수는 1, 2, 3, …이며, 약수도 양의 수만 다룬다.

예를 들어 18을 6으로 나누면 몫은 3이고 나머지는 0이다. 그래서 6은 18의 약수다. 24도 6으로 나누어떨어지므로 6은 두 수의 공약수다.

대상약수를 작은 것부터 나열
181, 2, 3, 6, 9, 18
241, 2, 3, 4, 6, 8, 12, 24
두 수의 공약수1, 2, 3, 6

마지막 줄의 가장 큰 수는 6이다. 그림 1은 표의 두 약수 목록을 두 원으로 겹쳐 놓은 것이다. 두 원이 겹친 부분의 1, 2, 3, 6이 공약수이고, 그중 가장 큰 6이 최대공약수다.

왼쪽 원은 18의 약수, 오른쪽 원은 24의 약수다. 겹친 부분의 1, 2, 3, 6이 두 수의 공약수이고, 테두리를 친 6이 최대공약수다.
그림 1 왼쪽 원은 18의 약수, 오른쪽 원은 24의 약수다. 겹친 부분의 1, 2, 3, 6이 두 수의 공약수이고, 테두리를 친 6이 최대공약수다. figures/divisor_venn.py

영어 이름 greatest common divisor를 줄여 GCD라고도 쓴다. 이 글에서는 최대공약수를 GG로 적는다.

18=6×3,24=6×4,G=6.(1)18=6\times3,\qquad24=6\times4,\qquad G=6. \tag{1}
정의
기호이름원어뜻
a,ba,b두 자연수natural numbers최대공약수를 구할 양의 정수 두 개
GG최대공약수greatest common divisora,ba,b의 공약수 중 가장 큰 수
232^32의 세제곱third power of two2를 세 번 곱한 2×2×22\times2\times2

식 (1)은 두 수를 6으로 나눈 몫이 각각 자연수임을 보여 준다. 1은 모든 자연수의 약수이므로 공약수 목록이 비는 경우는 없다. 공약수는 두 수 각각의 약수라서 어느 쪽 수보다도 클 수 없다.

최대공약수에서 왜 작은 지수를 택할까?

공약수의 소인수는 두 수 어느 쪽에도 부족하면 안 된다. 18에는 2가 한 개뿐이므로, 18과 24의 공약수에 2를 두 개 넣을 수는 없다.

먼저 두 수를 소인수분해한다. 거듭제곱의 지수는 같은 소수가 몇 번 곱해졌는지 세는 수다.

18=2×3×3=2×32,24=2×2×2×3=23×3.(2)\begin{aligned} 18&=2\times3\times3=2\times3^2,\\ 24&=2\times2\times2\times3=2^3\times3. \end{aligned} \tag{2}
  • 소인수 2는 18에 한 개, 24에 세 개 있다. 두 수에서 함께 고를 수 있는 것은 한 개다.
  • 소인수 3은 18에 두 개, 24에 한 개 있다. 두 수에서 함께 고를 수 있는 것은 한 개다.

따라서 공약수에 넣을 수 있는 소인수를 최대한 고르면 2 한 개와 3 한 개가 남는다.

G=2×3=6.(3)G=2\times3=6. \tag{3}
18과 24를 소인수 부품으로 나란히 놓았다. 왼쪽은 2, 오른쪽은 3의 자리다. 각 줄에서 강조한 2 한 개와 3 한 개를 공통으로 고르면 아래의 최대공약수 6이 된다.
그림 2 18과 24를 소인수 부품으로 나란히 놓았다. 왼쪽은 2, 오른쪽은 3의 자리다. 각 줄에서 강조한 2 한 개와 3 한 개를 공통으로 고르면 아래의 최대공약수 6이 된다. figures/common_prime_counts.py

그림 2에서 강조한 부품은 각 줄에서 하나씩 고른 2와 3이다. 다른 자연수 두 개에도 같은 이유가 적용된다. 공약수에는 두 수에 공통인 소인수만 들어갈 수 있고, 그 개수는 양쪽 중 적은 개수를 넘을 수 없다. 그 한도까지 모두 고른 곱은 두 수를 모두 나누어떨어지게 한다.

다른 공약수는 그 곱에서 소인수를 더 적게 고른 수이므로, 그 곱의 약수이며 더 클 수 없다. 따라서 공통인 소인수의 지수가 같으면 그대로, 다르면 작은 쪽을 택해 곱한다. 한쪽에만 있는 소인수는 넣지 않는다. 여기서 쓰는 근거는 소인수분해의 결과가 곱하는 순서를 빼면 하나로 정해진다는 성질이다.

공통인 소인수로 나누어도 최대공약수를 구할 수 있다

두 수를 공통인 소수로 나누어지는 동안 계속 나누면, 왼쪽에 적은 소수의 곱이 최대공약수다. 18과 24는 2로, 몫 9와 12는 다시 3으로 나누어진다. 남은 3과 4는 공약수가 1뿐이므로 G=2×3=6G=2\times3=6이다.

소인수분해의 세로 나눗셈을 두 수에 함께 쓰는 방법이다. 왼쪽에 적는 소수는 두 수를 모두 나누는 소수이므로, 그림 3의 왼쪽 열에는 두 수가 함께 가진 소인수만 쌓인다.

18과 24를 두 수의 공통인 소수 2와 3으로 차례로 나눈 세로 나눗셈. 남은 몫 3과 4는 공약수가 1뿐이라 멈추고, 왼쪽 소수의 곱 2×3=6이 최대공약수다.
그림 3 18과 24를 두 수의 공통인 소수 2와 3으로 차례로 나눈 세로 나눗셈. 남은 몫 3과 4는 공약수가 1뿐이라 멈추고, 왼쪽 소수의 곱 2×3=62\times3=6이 최대공약수다. figures/gcd_ladder.py

멈추는 시점은 남은 두 몫의 공약수가 1뿐일 때다. 3과 4 중 한쪽만 나누는 3이나 2로 더 나누지 않는다. 그렇게 나누면 다른 쪽에 없는 소인수가 왼쪽 열에 섞여 공약수가 아니게 된다. 남은 몫으로 다시 쓰면 18=6×318=6\times3, 24=6×424=6\times4로 식 (1)과 같다.

최대공약수로 두 수를 나눈 몫에는 공통인 소인수가 남지 않는다. 남아 있다면 그 소수를 한 번 더 곱한 더 큰 공약수가 있었을 것이기 때문이다. 그래서 18÷6=318\div6=3과 24÷6=424\div6=4처럼 몫의 공약수는 1뿐이고, 이 몫은 최소공배수를 구할 때 다시 쓰인다.

세 수나 거듭제곱 꼴에서도 작은 지수를 고른다

세 수의 최대공약수도 세 수 모두에 있는 소인수를, 세 수 중 가장 적은 개수만큼 골라 곱한다. 24, 36, 60에서는 2를 두 개, 3을 한 개 골라 최대공약수가 12다.

24=23×3,36=22×32,60=22×3×5(4)24=2^3\times3,\qquad36=2^2\times3^2,\qquad60=2^2\times3\times5 \tag{4}

그림 4에서 2는 세 줄에 3개, 2개, 2개 있으므로 가장 적은 2개를 고른다. 3은 1개, 2개, 1개라서 1개를 고른다. 5는 60에만 있어 고르지 않는다.

24, 36, 60의 소인수를 같은 소수끼리 세로로 맞췄다. 진한 동그라미는 세 줄 모두에서 고를 수 있는 2 두 개와 3 한 개이고, 이를 곱한 12가 최대공약수다. 60에만 있는 5는 고르지 않는다.
그림 4 24, 36, 60의 소인수를 같은 소수끼리 세로로 맞췄다. 진한 동그라미는 세 줄 모두에서 고를 수 있는 2 두 개와 3 한 개이고, 이를 곱한 12가 최대공약수다. 60에만 있는 5는 고르지 않는다. figures/gcd_three_numbers.py
G=22×3=12(5)G=2^2\times3=12 \tag{5}

수가 거듭제곱 꼴로 주어지면 곱을 계산하지 않고 지수만 비교한다. 23×32×72^3\times3^2\times7과 2×34×52\times3^4\times5라면 공통인 소인수 2와 3에서 작은 지수를 골라 2×32=182\times3^2=18이다. 7과 5는 한쪽에만 있어 넣지 않는다.

최대공약수를 알면 공약수를 모두 알 수 있다

두 자연수의 공약수 전체는 최대공약수의 약수 전체와 같다. 18과 24의 최대공약수가 6이므로, 공약수는 6의 약수인 1, 2, 3, 6이다. 그림 1의 겹친 부분이 바로 이 네 수다.

공약수는 앞에서 고른 최대 소인수 묶음에서 일부만 고른 수이므로 최대공약수의 약수다. 거꾸로 최대공약수의 약수는 최대공약수를 나누어떨어지게 하고, 최대공약수는 두 수를 나누어떨어지게 하므로 그 약수도 두 수를 나누어떨어지게 하는 공약수다. 예를 들어 6의 약수 3은 18과 24도 나누어떨어지게 한다. 6=3×26=3\times2이므로 18=6×3=3×2×3=3×618=6\times3=3\times2\times3=3\times6, 24=6×4=3×2×4=3×824=6\times4=3\times2\times4=3\times8로 바꿔 쓸 수 있기 때문이다.

그래서 공약수의 개수는 최대공약수의 약수의 개수와 같다. 소인수분해로 약수의 개수를 구하는 방법을 쓰면 6=2×36=2\times3의 약수는 (1+1)×(1+1)=4(1+1)\times(1+1)=4개다. 24, 36, 60의 공약수는 식 (5)의 12=22×312=2^2\times3의 약수 (2+1)×(1+1)=6(2+1)\times(1+1)=6개, 곧 1, 2, 3, 4, 6, 12다.

핵심

최대공약수는 두 자연수의 공통인 소인수를 각각 양쪽 중 적은 개수만큼 골라 곱한 수다. 공통인 소인수가 없으면 최대공약수는 1이다.

최대공약수가 1인 두 수를 왜 서로소라고 하나요?

두 수를 함께 나누어떨어지게 하는 1보다 큰 자연수가 없어서, 서로에 대해서는 소수(素數)처럼 더 쪼갤 공통 부분이 없기 때문이다. 서로소의 ‘소’가 소수의 ‘소’이고, 최대공약수가 1인 두 자연수를 서로소라고 한다. 8=238=2^3, 9=329=3^2은 공통인 소인수가 없어 공약수가 1뿐이므로, 둘 다 합성수인데도 서로소다. 서로소는 두 수 사이의 관계이고, 5와 7처럼 서로 다른 두 소수는 공약수가 1뿐이라 서로소다.

1이 포함되거나 두 수가 같아도 최대공약수를 구할 수 있나요?

1과 자연수 aa의 최대공약수는 1이다. 1의 양의 약수는 1뿐이기 때문이다. 같은 수 aa와 aa의 최대공약수는 aa이며, 예를 들어 12와 12의 최대공약수는 12다.

한 수가 다른 수의 약수이면 최대공약수는 무엇인가요?

두 자연수 중 한 수가 다른 수의 약수이면 작은 수가 최대공약수다. 예를 들어 6과 18에서는 6 자체가 공약수이고, 6의 약수가 6보다 클 수 없으므로 최대공약수는 6이다.

최대공약수의 흔한 오해

  • 공통인 소인수 중 가장 큰 소수만 고른다. — 18과 24에서 3만 고르면 공약수이기는 하지만 최대는 아니다. 공통으로 고를 수 있는 2도 곱해야 6이 된다.
  • 소인수의 지수까지 양쪽에서 더한다. — 18의 2 한 개와 24의 2 세 개를 합쳐 네 개 고를 수는 없다. 양쪽에서 각각 꺼낼 수 있는 같은 묶음을 고르는 것이므로 2는 한 개만 쓴다.

공통 부품을 고르는 이 방법과 반대로, 두 수에 필요한 부품을 모두 갖춘 수는 최소공배수에서 다룬다.

직접 해보기

  1. 20과 30의 최대공약수를 소인수분해로 구하자. 20에 있는 2를 모두 쓰지 않는 이유도 설명하자.
  2. 16과 25는 서로소일까? 각 수가 합성수라는 사실만으로 판단하지 말자.
  3. 32와 48의 공약수를 모두 구하자. 최대공약수를 먼저 찾은 뒤 그 약수를 쓰자.
  4. 22×33×52^2\times3^3\times5와 23×3×72^3\times3\times7의 최대공약수를 거듭제곱 꼴로 구하자.
  5. 42와 70을 공통인 소인수로 나누는 방법으로 최대공약수를 구하고, 공약수의 개수도 구하자.
답과 풀이
  1. 20=22×520=2^2\times5, 30=2×3×530=2\times3\times5다. 공통인 2는 적은 쪽인 한 개, 5도 한 개를 골라 최대공약수는 2×5=102\times5=10이다. 30에는 2가 한 개뿐이므로 공약수에 2를 두 개 넣을 수 없다. 실제로 20÷10=220\div10=2, 30÷10=330\div10=3이다.
  2. 16=2416=2^4, 25=5225=5^2라서 공통인 소인수가 없다. 최대공약수가 1이므로 서로소다.
  3. 32=2532=2^5, 48=24×348=2^4\times3이므로 공통인 2를 적은 쪽인 네 개 골라 최대공약수는 24=162^4=16이다. 3은 48에만 있어 넣지 않는다. 공약수 전체는 16의 약수 1, 2, 4, 8, 16이다.
  4. 공통인 소인수는 2와 3이다. 2는 지수 2와 3 중 작은 2, 3은 지수 3과 1 중 작은 1을 골라 22×3=122^2\times3=12다. 5와 7은 한쪽에만 있어 넣지 않는다.
  5. 42와 70을 2로 나누면 21과 35, 이를 다시 7로 나누면 3과 5가 남는다. 3과 5는 공약수가 1뿐이라 멈추고, 최대공약수는 2×7=142\times7=14다. 공약수는 14의 약수 1, 2, 7, 14로 (1+1)×(1+1)=4(1+1)\times(1+1)=4개다.

더 읽기

영상 노트

영상 노트
  • 00:00 두 상자에서 똑같은 소인수 묶음 고르기
  • 00:35 18과 24의 약수 목록과 그림 1의 겹친 부분에서 공약수 찾기
  • 01:30 식 (2)를 그림 2의 부품으로 펴고 식 (3) 얻기
  • 02:40 작은 지수보다 많이 고르면 어느 쪽에서 부족한지 설명하기
  • 03:30 그림 3의 세로 나눗셈으로 같은 6 구하기와 멈추는 시점
  • 04:30 식 (4)와 그림 4로 세 수 24, 36, 60의 최대공약수 12 구하기
  • 05:30 공약수 전체와 공약수의 개수를 최대공약수의 약수로 세기
  • 06:20 서로소·1의 경계와 새 연습 풀기

지도에서의 위치

완성예정이 페이지까지 온 길전체 지도에서 보기 →
이 페이지의 기록
  1. 2026-11-15 · 소인수의 개수로 최대공약수를 설명하고 서로소·공약수 전체·새 연습을 확인한 초안
  2. 2026-11-16 · 전수 검수 반영 — 약수 벤 다이어그램, 공통인 소인수로 나누는 방법, 세 수와 거듭제곱 꼴의 최대공약수, 공약수의 개수, 최대공약수의 약수가 공약수인 이유를 구체화, 서로소라는 이름의 뜻, 연습 입력 교체와 2문항 추가 (에이전트 수정, 그림 1→4)
  3. 2026-11-16 · 전수 검수(에이전트 편집·독립 검증) 통과 — 주인 요청으로 완성으로 올림