# 유클리드 호제법 분야: 대수 학교급: 중등 교육과정: 정규 교육과정 외 — 나눈 나머지를 되풀이해 최대공약수를 구하는 절차. 현존하는 가장 오래된 알고리즘이다. 정식 URL: https://pi.devxdev.xyz/wiki/math/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95 --- > 이 개념은 정규 교육과정 밖에서 다루어지는 내용으로, 나눈 나머지를 되풀이해 최대공약수를 구하는 절차이며 현존하는 가장 오래된 알고리즘으로 알려져 있다. ## 정의 두 자연수 $a$, $b$ (단, $a > b$)의 최대공약수 $\gcd(a, b)$(지시디 에이 비, $a$와 $b$의 최대공약수라 읽는다)를 구할 때, $a$를 $b$로 나눈 나머지를 $r$이라 하면 $$\gcd(a, b) = \gcd(b, r)$$ 이 성립한다. 이 관계를 나머지가 $0$이 될 때까지 반복하면, 마지막으로 나눈 수(즉 나머지가 $0$이 되기 바로 전 단계에서 나누는 수로 쓰인 값)가 두 수의 최대공약수가 된다. 이렇게 나눗셈과 나머지 구하기를 되풀이해서 최대공약수를 구하는 절차를 **유클리드 호제법**이라 한다. ## 직관 큰 수 두 개의 최대공약수를 소인수분해로 구하려면 먼저 각 수를 소인수분해해야 하는데, 수가 클수록 이 작업 자체가 오래 걸린다. 유클리드 호제법은 소인수분해를 전혀 하지 않고 **나눗셈만 반복**해서 최대공약수를 찾는다. 두 막대의 길이를 재는 상황을 떠올려 보자. 긴 막대에서 짧은 막대만큼을 계속 잘라내다 보면, 남는 부분(나머지)은 원래 두 막대보다 짧아진다. 이 "남는 부분과 짧은 막대"의 관계는 원래 두 막대의 관계와 똑같은 최대공약수를 가지고 있다. 그래서 문제를 점점 더 작은 숫자로 바꾸어 가다가, 결국 나누어떨어지는 순간에 답이 나오는 것이다. ## 유도 이미 알고 있는 것: 자연수 $a$를 자연수 $b$로 나누면 몫 $q$와 나머지 $r$이 정해져 $a = bq + r$ ($0 \le r < b$)로 쓸 수 있다(나눗셈). 그리고 $\gcd(a,b)$는 $a$와 $b$를 동시에 나누는 가장 큰 수다(최대공약수와 최소공배수). 여기서 막히는 점: $a$, $b$가 크면 두 수의 약수를 모두 나열하거나 소인수분해하는 데 시간이 오래 걸린다. 더 작은 수의 문제로 바꿀 방법이 필요하다. 돌파구: $a = bq + r$에서 $d$가 $a$와 $b$의 공약수라고 하자. $r = a - bq$이므로, $d$는 $a$도 나누고 $b$도 나누니 $bq$도 나누고, 따라서 그 차인 $r$도 나눈다. 즉 $a$, $b$의 공약수는 모두 $b$, $r$의 공약수다. 반대로 $d$가 $b$와 $r$의 공약수라면 $a = bq + r$에서 $bq$도 $r$도 나누어지므로 그 합인 $a$도 나눈다. 즉 $b$, $r$의 공약수는 모두 $a$, $b$의 공약수다. 양쪽 공약수의 집합이 완전히 같으니, 가장 큰 공약수도 같다: $$\gcd(a, b) = \gcd(b, r)$$ 예를 들어 $\gcd(1071, 462)$를 구해 보자. $1071 = 462 \times 2 + 147$ 이므로 $\gcd(1071,462) = \gcd(462, 147)$ $462 = 147 \times 3 + 21$ 이므로 $\gcd(462,147) = \gcd(147, 21)$ $147 = 21 \times 7 + 0$ 이므로 나머지가 $0$이 되었다. 나머지가 $0$이라는 것은 $147$이 $21$로 나누어떨어진다는 뜻이므로 $\gcd(147, 21) = 21$이다. 따라서 $\gcd(1071, 462) = 21$. 이렇게 "두 수를 나눈 나머지로 바꾸는" 과정을 나머지가 $0$이 될 때까지 반복하는 것이 유클리드 호제법이다. ## 예시 $\gcd(255, 105)$를 구해 보자. $255 = 105 \times 2 + 45$ $105 = 45 \times 2 + 15$ $45 = 15 \times 3 + 0$ 나머지가 $0$이 된 순간의 나누는 수 $15$가 최대공약수다. 즉 $\gcd(255, 105) = 15$. ## 🌍 실생활 예시 가로 $1071\,\text{cm}$, 세로 $462\,\text{cm}$인 벽면에 빈틈이나 잘림 없이 정사각형 타일만으로 채우려면 타일 한 변의 길이는 두 길이의 공약수여야 하고, 가장 큰 타일을 쓰려면 최대공약수를 알아야 한다. 위 유도에서 계산했듯 $\gcd(1071, 462) = 21$이므로, 한 변이 $21\,\text{cm}$인 정사각형 타일이 남는 부분 없이 가장 크게 채울 수 있는 크기다. ## ⚠️ 흔한 실수 - **잘못된 생각**: 매 단계마다 처음의 두 수 $a$, $b$를 계속 나눈다. → **왜 틀렸는지**: 유클리드 호제법은 매 단계마다 "나누는 수와 나머지"의 새로운 쌍으로 바꿔가며 반복해야 한다. 처음 두 수를 계속 쓰면 나머지가 줄어들지 않아 절차가 끝나지 않는다. - **잘못된 생각**: 나머지가 $0$으로 나온 그 나눗셈의 나머지, 즉 $0$이 최대공약수다. → **왜 틀렸는지**: $0$은 "여기서 멈추라"는 신호일 뿐이다. 최대공약수는 나머지가 $0$이 되기 바로 전 단계에서 나누는 수로 쓰인 값이다. - **잘못된 생각**: 계산 과정에서 나온 몫이 최대공약수를 나타낸다. → **왜 틀렸는지**: 다음 단계로 넘어갈 때 실제로 쓰이는 값은 나머지이고, 몫은 나눗셈 계산에만 쓰일 뿐 결과에 직접 나타나지 않는다. ## 확인 문제 1. 유클리드 호제법으로 $\gcd(84, 30)$을 구하라. 2. 유클리드 호제법으로 $\gcd(98, 56)$을 구하라. 3. $a$를 $b$로 나눈 나머지가 $0$이라면 왜 $b$가 곧바로 $a$와 $b$의 최대공약수가 되는지, 나눗셈의 나머지 정의를 이용해 설명하라. 정답 보기: 1. $84 = 30 \times 2 + 24$, $30 = 24 \times 1 + 6$, $24 = 6 \times 4 + 0$. 따라서 $\gcd(84,30) = 6$. 2. $98 = 56 \times 1 + 42$, $56 = 42 \times 1 + 14$, $42 = 14 \times 3 + 0$. 따라서 $\gcd(98,56) = 14$. 3. 나머지가 $0$이면 $a = bq$이므로 $b$는 $a$의 약수다. 또한 $b$는 자기 자신의 약수이므로 $b$는 $a$와 $b$의 공약수이고, $b$보다 큰 수는 $b$를 나눌 수 없으므로 $b$가 두 수의 공약수 중 가장 크다. ## 📜 역사 유클리드 호제법은 기원전 300년경 유클리드의 저서 「원론」 제7권에 두 양(길이)의 "공통 척도"를 구하는 방법으로 실려 있어, 오늘날까지 쓰이는 알고리즘 중 가장 오래된 것으로 알려져 있다. 당시에는 나눗셈의 나머지 대신 짧은 길이를 긴 길이에서 계속 빼는 방식으로 서술되었는데, 이는 지금의 나눗셈-나머지 방식과 본질적으로 같은 절차다. 이후 정수론이 발전하면서 뺄셈을 반복하는 대신 나눗셈 한 번으로 여러 번의 뺄셈을 대신하는 지금의 형태로 정리되었다. ## 관련 개념 - 나눗셈 - 최대공약수와 최소공배수 - 약수와 배수 - 소인수분해 - 정수와 유리수 --- 관련 개념: - 나눗셈 (/wiki/math/%EB%82%98%EB%88%97%EC%85%88) - 최대공약수와 최소공배수 (/wiki/math/%EC%B5%9C%EB%8C%80%EA%B3%B5%EC%95%BD%EC%88%98%EC%99%80_%EC%B5%9C%EC%86%8C%EA%B3%B5%EB%B0%B0%EC%88%98) - 약수와 배수 (/wiki/math/%EC%95%BD%EC%88%98%EC%99%80_%EB%B0%B0%EC%88%98) - 소인수분해 (/wiki/math/%EC%86%8C%EC%9D%B8%EC%88%98%EB%B6%84%ED%95%B4) - 정수와 유리수 (/wiki/math/%EC%A0%95%EC%88%98%EC%99%80_%EC%9C%A0%EB%A6%AC%EC%88%98)