최대공약수 구하기 (유클리드 알고리즘)

두수 사이에 최대공약수가 존재한다면,
$A와 $B 사이에는 최대공약수 $G를 가지는 수식이 완성된다.

인수분해

$A = $G * $x  
----- 1식
$B = $G * $y  ----- 2식



1식과 2식을 다시 표현하면,

$A - $B = ($G * $x) - ($G *$y) = $G * ($x - $y) ----- 3
식
$A % $B = ($G * $x) % ($G *$y) = $G * ($x % $y) ----- 4식



3식에서, $A와 $B가 최대공약수를 가지면, $A-$B도 $A와 $B가 가지는 최
대공약수를 같이 같는다.
$G = GCD($A, $B) = GCD($A - $B, $B)  = GCD($B, $A)

4식에서, $A와 $B가 최대공약수를 가지면, $A%$B도 $A와 $B가 가지는
최대공약수를 같이 같는다.
$G = GCD($A, $B) = GCD($A % $B, $B)  = GCD($B, $A)

즉, $G = GCD($A, 0) = $A 가 성립되는 것이다. ( 0은 어떤수와 곱
해도 0이기 때문)


< ?php
function get_cgd($u, $v)  
{  
    $t = 0;  

    while($v) {  
        $t = $u % $v;
      
$u = $v;  
        $v = $t;
    }  
    return $u;  
}
?>

echo get_cgd(45, 10);