使用辗转相除法(Euclidean algorithm)求两个数的最大公约数(Greatest common divisor)

以下都是我个人的理解，
如果有哪里不对的地方还请赐教（

记住一个公式是 $$ a = b \cdot q + r $$
其中a和b就是要被求GCD的两个数字。

举个例子，比如我要求gcd(90,65)，则得出： $$ 90 = 65 \cdot q + r $$
那么经过计算式子1，得到 $ q = 1 $ ，$ r = 15 $，即 $ 90 = 65 \cdot 1 + 15 $。
接下来，把 $ 90 = 65 \cdot 1 + 15 $ 中的 b 赋值予 a ，r 赋值予 b ，再塞回那个公式里，得到 $$ 65 = 15 \cdot q + r $$
继续计算，得到 $ q = 4 $ ， $r = 5 $。即 $65 = 15 \cdot 4 + 5 $ 。
然后不断重复上述步骤，一直到 $r = 0$ 。
当 $r = 0$ 时，它上一条的r就是这个两个数的最大公约数了。

比如这样

一个php的实现：

<?php  
  
function gcd($a, $b) {  
    calculate: $r = $a % $b;  
    if ($r <> 0) {  
        $a = $b;  
        $b = $r;  
        goto calculate;  
    }  
    else if ($r == 0) {  
        return $b;  
    }  
}