유클리드 호제법이란?호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.호제법(互除法)이라는 단어가 따로 있는것은 아니고, 서로(互) 나누기(除) 때문에 붙여진 이름이다. 유클리드 호제법의 정의는 다음과 같다.자연수 a, b에 대해서 a를 b로 나눈나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 즉,  gcd(a, b)=gcd(b,r) 이라고 나타낼 수 있다.영어로 유클리드 호제법은 Euclidean algorithm 이다. 말 그대로 알고리즘이기 때문에, 유클리드 호제법을 한번만 사용해서는 큰 의미가 없고,, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 ..