유클리드 호제법은 두 수의 최대공약수를 효율적으로 구하는 알고리즘이다. 고대 그리스의 수학자 유클리드가 제안한 이 방법은 유클리드의 저서인 '원주율에 관한 책(The Elements)'에서 처음 소개되었다.

유클리드 호제법의 기본 원리는 다음과 같다. 두 수 a와 b (단, a ≥ b)가 주어질 때, a와 b의 최대공약수는 b와 a를 b로 나눈 나머지 r의 최대공약수와 동일하다는 것이다. 이를 수식으로 표현하면, GCD(a, b) = GCD(b, r)이며, 마지막으로 r이 0이 될 때 b가 최대공약수이다.

구체적인 절차는 다음과 같다.

1. 두 수 a와 b를 정한다 (a ≥ b).

2. a를 b로 나눈 나머지 r을 계산한다.

3. 만약 r이 0이면, b가 최대공약수이다. 그렇지 않으면, a를 b로, b를 r로 바꾸고 2단계로 돌아간다.

이 과정을 반복함으로써 최대공약수를 찾아낼 수 있다. 유클리드 호제법은 간단하면서도 효율적이며, 두 수가 매우 커도 빠른 속도로 최대공약수를 계산할 수 있다는 장점이 있다. 현대의 컴퓨터 알고리즘에서도 널리 사용되며, 원주율, 분수의 약분, 문제의 수학적 최적화 등 다양한 분야에서 응용된다.