유클리드의 호제법은 쉽게 말해서 최대공약수를 구하는 알고리즘이다. A와 B의 최대공약수를 구한다면, A=QB+R 위 식처럼 A와 B의 관계를 나타내도록한다.(A>B) 이상태에서 다시 제수(B)과 나머지(R)의 관계를 같은 형식으로 나타내보자. B=Q'R+R' 나머지로 제수를 계속해서 나눠간다. 이렇게 반복하다보면 언젠가 제수가 딱 떨어지는 순간이 생기게된다. 생각해 보면 모든 수에대하여 성립한다. 이 때 떨어지는 순간 제수가 최대 공약수가 된다는 것이 호제법이다. 연습삼아 유클리드 호제법으로 최대공약수를 구해보자. *제수:나누는 수 *피제수:나눔을 당하는수 *나머지:나머지 GCD(3,6) 2 = 6/3...0 나머지가 0일때 제수가 3이므로 GCD는 3 GCD(8,28) 3 = 28 / 8...4 2 =..
