Lesson goal: The Greatest Common Divisor (GCD)

Previous: Convert between Celsius and Fahrenheit | Home | Next: Reducing fractions with the GCD

Do you remember a concept called the "greatest common divisor" (GCD) from math class? The name is confusing, and it's often hard to remember the difference between this and something else called the "least common multiple" or LCM.

Well, the GCD is a property of two numbers: it is the largest number that divides evenly into both numbers. So, the GCD of 20 and 12 is 4. That of 54 and 24 is 6. Let's write a function that will find the GCD of two numbers and return its result. The method we'll use here is very inefficient and definitely a simplisitc way to find a GCD on a computer, but it works and it's instructive. It's also represents more-or-less how you find GCDs in math class: by guessing and checking.

Suppose we wrote a function called gcd that took in two integers, called $a$ and $b$, where $a< b$. We'll start our initial GCD guess, $g$ at $1$ via the g=1 line. Next, we'll start a for-loop and count through all integers from $1$ to $a$. We'll stop at $a$ because the GCD cannot possibly be larger than the smaller of the two numbers for which we want the GCD.

Now for the good part. Remember the "remainder" or "mod" operator from this lesson? This operator, which (the % sign) divides two numbers and tells us the remainder of the division. Since we are looking to see if one number divides evenly into another, we are looking for the % operator to give us a $0$ (zero), since a zero remainder means the two numbers divided evenly into one another.

Now, as our for-loop is counting up the integers we'll see if it divides evenly into both $a$ and $b$. If it does, then $i$ could potentially be the GCD, as we should "save" it into our temporary guess, $g$. If not, we'll keep counting up to $a$ and see if we find a larger number that divides evenly into both $a$ and $b$.

Now you try. What compound condition will you put into the if statement to test if both a and b divide evenly into our trial GCD in variable i?

Type your code here:

See your results here: