程序实现：

    private static int gcd(int p, int q) {
        if (q == 0) {
            return p;
        } else {
            return gcd(q, p % q);
        }
    }

证明

求证 gcd(p,q) = gcd(q,p%q)，其中p,q都是正整数。¹

证：
令p=kq+r
设d是p和q的一个公约数，记作d|p，d|q
令正整数m=p/d=kq/d+r/d
∵kq/d,m∈Z*
∴r/d∈Z*
∴d|r
∴p与q的公约数也是p与r（即p%q）的公约数
（但是此时无法证明p与q的`最大`公约数是q与r的`最大`公约数）
（设p与q的公约数集合为A，q与r的公约数集合为B，此时得到A⊆B，要证明题目，还需要进一步证明B⊆A，则A=B，则可退知max（A）=max（B），即得证）
设d'是q与r的公约数
∴p/d'=kq/d'+r/d'
∴d'|p
∴q与r的公约数也是p与q的公约数
∴gcd(p,q)=gcd(q,p%q)