유클리드 호제법 2개의 자연수 또는 정수의 최대공약수 를 구하는 알고리즘의 하나이다. 호제법 이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이다. 2개의 자연수 a, b 가 있다고 했을 때 a 를 b 로 나눈 나머지 를 r 이라고 하면 (단, a>b ) a 와 b 의 최대공약수 는 b 와 r 의 최대공약수 와 같다. b 를 r 로 나눈 나머지 를 r’ → r 을 r’ 로 나눈 나머지 위의 과정을 반복해서 나머지가 0이 되었을 때의 수가 a 와 b 의 최대공약수 이다. 이런 과정을 거쳐 다음 정리를 이용해서 유클리드 호제법 이 성립하게 된다. 정리 a, b 는 정수, a 를 b 로 나눈 나머지가 r 이라고 하자. ( a ≥ b , r은 0 ≤ r < b 인 정수) a 와 b ..