5 BAEKJOON) 유클리드 호제법

<유클리드 호제법>
     : 최대공약수 구하는 방법

pf) G:최대공약수

     a,b가 자연수(a>b)
     a=bq+r일 때, GCD(a,b)=GCD(b,r)이다. // GCD : Greateast Common Divisor


     초기 설정1)a=AG, b=BG(A와 B는 서로소)
     초기 설정2)a>b이므로 a=bq+r (q!=0)
     G=GCD(a,b)=GCD(b,r)임을 보이자

     AG=BGq+r, G(A-Bq)=r
     GCD(b,r)=GCD(BG, G(A-Bq))
     GCD(b,r)에서 G가 최대공약수이려면 (A-Bq)와 B가 서로소이어야한다.

         *귀류법을 이용하여 증명해보자.

     만약, A-Bq, B가 서로소가 아니라면 B=ky, A-Bq=kx라고 할 수 있다.
     이때 k(x+qy)=A이고 B=ky이다.
     A와 B는 서로소가 아니다.(k로 나뉘므로)
     그런데, 위에서 A와 B는 서로소임을 정의했으므로 모순이다.

     귀류법에 의해 A-Bq와 B가 서로소이어야한다.
     따라서 r=G(A-Bq), b=BG는 최대공약수가 G가 되므로 
     GCD(a,b)=GCD(b,r)이다. (a>b)


<유클리드 호제법의 알고리즘 구현>
     GCD(A,B)=GCD(B, A%B)이고,
         if(A%B)=0 -> GCD=B
         else GCD(B, A%B)

     재귀함수 꼴로 구현 할 수 있으며 이때 함수 종료조건은 (A%B==0)인 것이다.

<유클리드 호제법으로 최소공배수 구하기>
     최소공배수와 최대공약수의 곱은 두 수의 곱과 같다. 최대공약수를 구한 후 이를 이용하여 최소공배수를 구할 수 있다.

     pf) A=Ga, B=Gb (a,b는 서로소) 일때 
         (G^2)ab/G=Gab