두수 사이에 최대공약수가 존재한다면,
$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);
|
|
추천 : 