유클리드 호제법이란?유클리드 호제법(Euclidean algorithm)은 유클리드 알고리즘이라고도 불리우며,두 양의 정수 혹은 자연수의 최대공약수(GCD, Greatest Common Divisor)를 구하는 효율적인 알고리즘이다.그리스 수학자 유클리드((Euclid)가 작성한 원론에 적혀있는 내용으로, 인류 최초의 알고리즘이라고 한다.   원리GCD(a,b)=GCD(b,amodb) 두 수 a와 b (a>b)의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다.이 과정을 반복하여 나머지가0이 될 때 나누는 수가 두 수의 최대공약수이다.  큰 수인 a를 b로 나눈 나머지 r을 구한다.a를 b로 대체하고, b를 r로 대체한다.나머지 r이 0이 될 때까지 반복한다.나머지가 0이 되었을 때, 나누는..