유클리드 호제법(Euclidean algorithm)

유클리드 호제법은 2개의 자연수 사이의 최대공약수를 구할 때 사용하는 알고리즘이다.


2개의 자연수 a, b(a > b)가 있고 a % b = r 이라고 한다면 a, b의 최대공약수는 a, r의 최대공약수와 같다. 이 성질을 이용해 b를 r로 나눈 나머지 r’을 구하고 다시 r을 r’으로 나눈 나머지를 구하는 과정을 반복해서 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수라고 한다.