Finding Greatest Common Factors with the Euclidean Algorithm

Usually when we find the Greatest Common Factor between two numbers, we find the prime number fingerprints of our two numbers and see which prime numbers they have in common. Here is the process for finding the GCF of 81 and 57:

We'd then see which primes our two numbers share:

And find that the CGF of 81 and 57 is 3.

But what if we have students who have trouble with multiplication so that finding prime numbers is hard? Or what if this method just isn't working for a student for some other unknown reason? 

I love presenting different methods to students so that they have options. One option is to post and reinforce divisibility rules, giving students calculators and having them repeatedly divide 81 and 57 by each prime number, recording and comparing the primes lists. Another option is.... Euclid!

Euclid was born 2300 years ago in Greece and is widely accepted as one of the greatest mathematicians ever. One of his developments was what we now call the Euclidean Algorithm for finding the GCF. Here is Euclid's Algorithm in action for 81 and 57:

Using 81 and 57 as an example, we find how many times 57 divides into 81, record that number and the remainder. 57 divides into 81 once with a remainder of 24.

We then find how many times 24 divides into 57, record that number and the remainder. 24 divides into 57 twice with a remainder of 9.

This process continues until we get a remainder of zero. The previous remainder is the GCF!

If your students are learning about GCFs, I made this GCF, LCM and Prime Factors pennant for them to show off their learning. 

You can download the Euclidean Algorithm example and speech bubble posters seen in this post from my resource library.