서론 크.... 내가 유클리드 호제법에 대해서 포스팅하는 날이 올줄이야... 상상도 못했다 ㅋㅋㅋ 이론 임의의 두 정수가 있을 때 두 정수의 최대공약수를 구하는 방법 중 하나가 유클리드 호제법이다. 여기서 최대공약수는 Greatest Common Divisor이며, 보통 GCD라고 이야기한다. 이를 간단히 식으로 표현해보면 a mod b = r = GCD(a, b) = GCD(b, r) 이다. 이론 자체는 매우 쉽다. 증명하기가 어려워서 그렇지... ㅋㅋ 방식은 아래와 같다. 임의의 정수 a와 b가 a > b라고 가정하자. 이 때 b로 a를 나눈 나머지를 r1이라고 하자. 이 r1으로 다시 b를 나누고 이 나머지를 r2라고 하자. 이 r2로 다시 r1을 나누고... 이렇게 나눠 나머지가 0이 될때까지 반..