Euclid's division theorem

Would you imagine a theorem invented as early as 600 BC is still used widely? Jim Massey in his course notes mentions that, this is the single most important theorem in mathematics (applied math as well) which stood against the test of this long a time gap. Frankly, I began to appreciate it more now (with the Abstract algebra course currently going...). Barely ever I had an idea that this is invented in the BC. However, the algorithm was probably not discovered by Euclid and it may have been known up to 200 years earlier. Historians claim that Aristotle was aware of this fact (which is 330 BC or so)

Since we are in the age of programming, let us write the algorithmic steps, rather than the math: The original algorithm of Euclid is,

function gcd(a, b)
    while b ≠ 0
        if a > b
            a := a - b
        else
            b := b - a
    return a

But we can simply write this in modern algebraic terms as

function gcd(a, b)
    if b = 0 return a
    else return gcd(b, a mod b)