Another way of computing the gcd of 2 integers

Here is a function (in Python) which (hopefully) returns the gcd of two positive integers a and b:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def bgcd(a,b):
    arg1=int(a)
    arg2=int(b)
    factor = 1
    while arg1 != arg2:
        while (arg1 & 1 ==0) and  (arg2 & 1 ==0):
            arg1 /=2
            arg2 /=2
            factor*=2
        while arg2 & 1 ==0:
            arg2 /= 2
        while arg1 & 1 ==0:
            arg1 /=2
        if arg1 & 1 ==1 and arg2 & 1 == 1:
            mean=(arg1+arg2)/2
            if arg1 < arg2:
                arg2 = mean
             else:
                arg1=mean
    return factor * arg1

Assuming $a$ and $b$ are distinct positive integers, on each iteration of the loop starting on line 5 $arg1 +arg2$ gets smaller.

• If $a$ and $b$ both are even, then $\frac{a}{2} +\frac{b}{2} < a +b$.
• If both $a$ and $b$ are odd, then $\textrm{min}(a,b) +\frac{a+b}{2} =a+b -\frac{\lvert a-b\rvert}{2} < a+b$

The same goes when $a$ and $b$ are of opposite parity.

Suppose $a$ and $b$ are distinct positive integers not both even. If $d$ is a common divisor of $a$ and $b$, then $d$ must also be odd.

• If both $a$ and $b$ are odd, then $a +b$ is even. Let $r$ be the largest power of 2 dividing $a +b$. Since $2^{r}$ and $d$ are relative prime, then $d$ is a divisor of $\frac{a+b}{2^{r}}$. Therefore $d$ is also a divisor of $\frac{a+b}{2}$ and of $\textrm{min}(a,b)$.

• By a similar argument, one can see that $d$ is a common divisor of $a$ and $\frac{b}{2}$ (resp. $\frac{a}{2}$ and $b$) in case of $a$ and $b$ having opposite parity.

So if $d$ is a common divisor of $a$ and $b$, then $d$ also is a divisor of the value returned by the bgcd function.

Lemma: Let $m$ and (n) be non-zero integers such that $m \mid n$ and $n \mid m$. Then $m=n$ or (m=-n).

Letting m=\textrm{gcd(a,b), and $n$ the value returned by the bgcd function, we need to show $n \mid m$. From the definition of the greatest common divisor it follows that if n \mid a) and \(n \mid b), then \(n \mid m. Clearly this is the case when $a=b$. So we are left with the cases $a < b$, $b < a$. Suppose $a < b$. Then $m=\textrm{gcd}(a, b \bmod{a})$.