Greatest Common Denomintor function not making sense

Question

There is a function I found that works but I do not understand why it works. I think it should output 8 but instead it is giving me the correct answer of 4. This is Python by the way.

def gcd (a, b):
    while(b != 0):
        t = b
        a = b
        b = t % b

return a

Again, when a = 8 and b = 20, it correctly spits out 4 but when I do print(8 % 20) it spits out 8. so what am I missing?

Answer 1

What you here specify is Euclidean method [wiki]. There is a typo in your code, it should be:

def gcd (a, b):
    while(b != 0):
        t = a
        a = b
        b = t % b
    return a

Note that it "swaps" a and b in each iteration. Indeed, if you call gcd(8, 10) than before the first loop a = 8 and b = 20.

Then after the first iteration a = 20 and b = 8 % 20, so after the first iteration a = 20 and b = 8. The next round we calculate a = 8 and b = 20 % 8, this is equal to b = 4. Then finally the final round will set a = 4 and b = 8 % 4 so b = 0 and we can stop.

As is specified by the Wikipedia article, it works based on the fact that:

The Euclidean algorithm is based on the principle that the greatest common divisor of two numbers does not change if the larger number is replaced by its difference with the smaller number.

In other words, it means that if a < b then gcd(a, b) = gcd(a, b - a). We can keep subtracting a from b until we reach a value between 0 and b, hence gcd(a, b) = gcd(a, b mod a). Since we know that a mod b is between 0 (inclusive) and b (exclusive), we can thus swap the two numbers to ensure that the largest of the two is again positioned first. We can continue with that until we hit zero for the smallest one.