Fast Coprime Checker

Today, I began thinking of coprime numbers, or numbers with a gcd of 1.  Coprime numbers, also known as relatively prime numbers, are important because if you want a fraction in reduced form, like 4/10 -> 2/5, the numerator and denominator must be relatively prime, or coprime. 

I wanted to find a good algorithm for determining whether two numbers were coprime. Obviously, you could do this in python, as gcd is in the fractions module:

rprime = lambda a,b: gcd(a,b) == 1

However, I wanted to code it without importing a module. Two coprime numbers have a GCD of 1, so by using the Euclidean algorithm (aforementioned in "Basic Math Operations Done in Python"), checking whether two numbers were coprime would become much easier. 

def rprime(a,b):
    while b: #b != 0
        a,b = b, a%b
    return a == 1

The algorithm above is essentially the same speed as the gcd function in the module fractions, as it uses the same algorithm. (I checked using inspect.getsource(fractions.gcd))

What this function does is it replaces numbers a and b, with the smaller number, and the remainder of the larger number divided by the smaller number. 

So, this is what would happen when you try to see if 324 and 4881 are relatively prime.

1. 4881 324
2. 324 21
3. 21 9
4. 9 3
5. 3 0

So, now when there is one zero, it means that the previous two numbers were multiples, so the GCF is the previous small number. So, since the GCF of 324 and 4881 is 3, they aren't relatively prime. This is a very good coprime check, as it is very short to code and is fast.