최대공약수를 구하는 방법 중에 유클리드가 다음의 방법을 발견했는데요. 이러한 유클리드 호제법은 프로그래밍 구현시 가장 자주 사용되는 수학적 원리가 되고 있습니다. 유클리드는 a와 b의 두수의 최대 공약수는 b와 a를 b로 나눈 나머지의 최대 공약수라는 것을 발견했는데요. 이것을 증명하는 것은 간단합니다. 공통된 최대공약수를 g라고 하면 a = g * x b = g * y 라고 하면 g가 최대 공약수이기 때문에 x와 y는 공약수가 1 밖에 없는 서로소가 됩니다. ----(1) 따라서 a = b*q + r 이라고 하면 (여기서 a가 b보다 크다고 가정을 했습니다.) b = g*y 이므로 a=q*g*y + r 이 되고 a= g*x 이므로 g*x=q*g*y + r 이 됩니다. 따라서 다음과 같이 식을 만들 수 ..
