개발여행의 블로그

유클리드 호제법 (유클리드 알고리즘)은 2개의 자연수의 최대공약수를 구하는 알고리즘이다. * 최대공약수 : GCD(Greatest Common Divisor) 양의 정수 A, B가 존재하고 A가 B보다 크다는 전제하에 A를 B로 나눈 나머지를 r이라고 칭한다. 이때 A와 B의 최대공약수는 B와 r 사이의 최대공약수와 같다. 이것이 유클리드 호제법이다. 그 이유를 살펴보자! A는 어떤 수 * 최대공약수, B는 어떤 수 * 최대공약수로 나타낼 수 있다. 즉 아래와 같이 나타낼 수 있다. (최대공약수이기 때문에 더 이상 약수는 존재하지 않아야 하므로 a와 b는 서로소이다.) 여기서 증명해야 할 것은 A와 B의 최대공약수는 G이므로 A를 B로 나눈 나머지가 r이었을 때, B와 r의 최대공약수도 G인지 확인해야 ..