Greatest Common Divisor

Description

The Greatest Common Divisor (GCD), sometimes known as the highest common factor, is the largest number which divides two positive integers (a,b). For a = 12, b = 8 we can calculate the divisors of a: {1,2,3,4,6,12} and the divisors of b: {1,2,4,8}. Comparing these two, we see that gcd(a,b) = 4. Now imagine we take a = 11, b = 17. Both a and b are prime numbers. As a prime number has only itself and 1 as divisors, gcd(a,b) = 1. We say that for any two integers a,b, if gcd(a,b) = 1 then a and b are coprime integers. If a and b are prime, they are also coprime. If a is prime and b < a then a and b are coprime. 🔆 Think about the case for a prime and b > a, why are these not necessarily coprime? There are many tools to calculate the GCD of two integers, but for this task we recommend looking up Euclid's Algorithm. Try coding it up; it's only a couple of lines. Use a = 12, b = 8 to test it. Now calculate gcd(a,b) for a = 66528, b = 52920 and enter it below.

Mr. Euclid, Sir

To answer the first quiz question, if b > a and a is prime, then it is possible that b is a multiple of a, so the GCD of these two numbers is a and they are not coprime.

Let's take a look at Euclid's Algorithm

Euclidean Algorithm

We are given two positive integers a and b, assume that a > b

  1. Divide a / b to get the remainder r and if r = 0, b is the GCD of a, b

  2. Else, replace a with b and b with r, then repeat

Proof

We can prove this by induction, but intuitively this algorithm will eventually terminate as the remainder r will inevitably decrease and eventually reach 0

Equivalently, we have a=q0b+r0b=q1r0+r1r0=q2r1+r2a = q_0b+r_0 \rightarrow b = q_1r_0 +r_1 \rightarrow r_0=q_2r_1+r_2 \cdots

Eventually, we get rn=0r_n=0 which implies rn1=gcd(a,b)r_{n-1}=gcd(a,b)

We wish to prove rn1=gcd(a,b)=gr_{n-1}=gcd(a,b)=g

  1. rn1gr_{n-1}\leq g

    Since rn=0r_n=0 we know rn2=qnrn1r_{n-2}=q_nr_{n-1} and rn1r_{n-1} divides rn2r_{n-2}

    Thus we can also get rn3=qn1rn2+rn1=qn1qnrn1+rn1r_{n-3}=q_{n-1}r_{n-2}+r_{n-1}=q_{n-1}q_nr_{n-1}+r_{n-1} and rn1r_{n-1} also divides rn3r_{n-3}

    We can repeat this to get that rn1r_{n-1} divides aa and bb, and thus is a common divisor It follows that rn1gr_{n-1} \leq g, the greatest common divisor

  2. rn1gr_{n-1}\geq g

    For any common divisor cc we have a=mca=mc and b=ncb=nc

    Then cc divides r0r_0 since r0=aq0b=mcq0nc=(mq0n)cr_0=a-q_0b=mc-q_0nc=(m-q_0n)c

    We can repeat this argument to get that cc divides rn1r_{n-1}, so it follows that gg divides rn1r_{n-1} as it is also a common divisor It follows that rn1gr_{n-1}\geq g

From both of these statements, we conclude rn1=gr_{n-1}=g

Implementation

def gcd(a, b):
    # Only works if a > b
    if a < b:
        return gcd(b, a)

    # Euclidean algorithm
    while b != 0:
        # Calculate r = a % b
        # Set a = b
        # Set b = r
        a, b = b, a % b
    
    return a
    
print(gcd(66528, 52920))

Though of course, if you're lazy you can use an online tool

Flag

1512

Last updated