이 개념은 정규 교육과정 밖에서 다루어지는 내용으로, 나눈 나머지를 되풀이해 최대공약수를 구하는 절차이며 현존하는 가장 오래된 알고리즘으로 알려져 있다.
두 자연수 $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}$인 정사각형 타일이 남는 부분 없이 가장 크게 채울 수 있는 크기다.
유클리드 호제법은 기원전 300년경 유클리드의 저서 「원론」 제7권에 두 양(길이)의 "공통 척도"를 구하는 방법으로 실려 있어, 오늘날까지 쓰이는 알고리즘 중 가장 오래된 것으로 알려져 있다. 당시에는 나눗셈의 나머지 대신 짧은 길이를 긴 길이에서 계속 빼는 방식으로 서술되었는데, 이는 지금의 나눗셈-나머지 방식과 본질적으로 같은 절차다. 이후 정수론이 발전하면서 뺄셈을 반복하는 대신 나눗셈 한 번으로 여러 번의 뺄셈을 대신하는 지금의 형태로 정리되었다.