Home » Education

Finding the GCF of Numbers

Ranked #7,465 in Education, #171,002 overall

How to get the GCF of Two or More Numbers

Learning how to get the Greatest Common Factor (also known as Greatest Common Multiple) is first learned in High School Algebra. This is because the principle of the GCF can be used to get the LCM (Least common multiple) and therefore the GCD (Greatest Common Denominator) of a fraction. At this point, it is taught through prime factorization. I'll be honest, I think learning the GCF at the high school algebra level is pointless. You can use prime factorization to get the LCM yourself anyway, so the GCF is really just another thing to learn.

Math and other science majors in University may also end up relearning how to get the GCF of a number as it can be used for encryption, decryption, and various modular arithmetics. However, at this point, another method called the Euclidean Algorithm is used as it can handle large numbers better than the prime factorization method. It's not a particularly hard method, so if you're a high school student, feel free to learn it.

GCF Calculator

Greatest Common Factor Calculator
Calculate the GCF of 2 or more values. How to find the greatest common factor using factoring, prime factorization, Euclid's Algorithm and PHP Programming.

Prime Factorization

High School Level Algebra

To find the Greatest Common Factor of two, or more, numbers, you need to know their prime factorization.

What is Prime Factorization?
Every number is a product of prime numbers. A prime number is a number that can only be a product of 1 and itself
Prime Factorization is writing a number solely using its primes .

Example:
2: 1 * 2 (prime)
4: 2 * 2
3: 1 * 3 (prime)
5: 1 * 4 (prime)
6: 2 * 3
90: 2* 3 * 3 * 5



How to Get the Prime Factorization of a Number
Remember back in elementary school where you learned how to tell if numbers were divisible by 2,3,5, etc..? Well, you might need those skills.
Basically, in order to prime factorize, you figure out a number that definitely goes into a number and keep dividing until you get all primes. This is called a prime factorization tree.

GCFof180

Example:
180: Notice how it finishes in 0? It's divisible by 10
Factorization 1: 18 * 10

10: We all know 10 is 2 * 5
Factorization 2: 18 * (2 * 5)

18: You may say 3 * 6 or 2 * 9. It doesn't really matter. I'll pick 3 * 6 because that's the first one I thought of
Factorization 3: (3 * 6) * (2 * 5)

6: That's 2 times 3
Factorization 4: (3 * [2 * 3]) * (2 * 5)

Factorization: 180 = 3 * 2 * 3 * 2 * 5
That looks messy, so let's order them.
Factorization: 180 = 2 * 2 * 3 * 3 * 5



What if I can't figure out a number?
Get your calculator out and try dividing by some of the prime numbers whose tricks you don't know?

Example: 217
Most people don't know the tricks for Divisibility by 7, and definitely not for Divisibility by 31! This one would need some guessing.
We know it's not divisible by 2,3, or 5.
So let's try 7!
217 / 7 is 31. 31 is a prime number (you should know all the prime numbers up to and including 31)



Examples:
Prime factorization of 245: 5 * 7 * 7
The prime factorization of 36 is: 2 * 2 * 3 * 3

More commonly asked examples: Prime factorization of
125 = 5 * 5 * 5
120 = 2 * 2 * 2 * 3 * 5
225 = 3 * 3 * 5 * 5
40 = 2 * 2 * 2 * 5
63 = 3 * 3 * 7

Prime Factorization Calculator

Prime Factorization Calculator
Calculator to find prime factors of integers. Performs the prime decomposition of numbers showing results in simple and power form. Also creates a factor tree to show the work. Factorization of numbers into its prime numbers. Free online calculators.

Using Prime Factorization to get the GCF

Using Prime Factorization to get the GCF
I will give your the prime factorization of two numbers (I'm so nice) and you will need to tell me their Greatest Common Factor

6300 = 2*2*3*3*5*5*7
330 = 2*3*5*11
GCF = 30. Can you see why?

Well it's actually simple!
You multiply by the factors in common, and by the most it arrives in both numbers. (so in this example 2 is in both numbers, it's one time in 330 and two times in 6300. So the most it appears in both numbers is one time)

Example
2 * 2 * 3 * 3 * 5 * 5 * 7
2 * 3 * 5 * 11
Multiply them:
2*3*5 = 30!



What if there are more than 2 numbers?
Just find the ones that are the same, like before:

Example
1140: 2 * 2 * 3 * 5 * 19
40: 2 * 2 * 2 * 5
360: 2 * 2 * 2 * 3 * 3 * 5

becomes
2 * 2 * 3 * 5 * 19
2 * 2 * 2 * 5
2 * 2 * 2 * 3 * 3 * 5

GCF: 2 * 2 * 5

GCF: 2 * 2 * 5 = 20

GCF by Algorithm

There's an algorithm for figuring out the GCF. If you're in High School, your teachers will not expect you to use this. If you're in a university level class taking a Math 200 or 300 level course (Asbtract Algebra, Foundations of Advanced Mathematics, Discrete Mathematics are such possible courses), you might be asked to learn this.

It's called the Euclidean Algorithm.

Here's how it works:
  • You set up two numbers in the form A = f * B + r, where A and B are your numbers, f is a product, and r is the remainder

  • Bring it down over, where B becomes the equal, and R becomes B2 (B = f* B2 + r)

  • Keep going until you reach a remainder of 0

  • The remainder above the remainder of 0 is the GCF

  • This makes a lot more sense when you see it in action



euclidean-gcf

Example:

Example:
Let's do 6300 and 330
6300 = f * 330 + r
Divide 6300 by 330 to get its factor (19). Now get the remainder by doing 6300 - 19*330 to get 30
6300 = 19 * 330 + 30

Bring 330 and 30 down
330 = f * 30 + r
Divide 330 by 30 to get its factor (11). Now get the remainder by doing 330 - 11*30 to get 0
330 = 11*30 + 0

Look at the chain:
6300 = 19 * 330 + 30
330 = 11*30 + 0
See where the remainder of 0 is? Well the remainder above it (30) is the GCF.
GCF: 30



And if I have multiple numbers?
That's where it gets tricky. You have to find the GCF of the first pair, then the second pair, then the third pair, etc...
Then you have to find the GCF of those GCFs until only one GCF remains!

Let's pick something easy.

multiple-euclidean

Example:
12, 18, 150, 210.
The Pairs are therefore: 12&18, 18&150, 150&210 (just read them normally)

12 & 18
18 = 1 * 12 + 6 <= GCF = 6
12 = 2 * 6 + 0

18 & 150
150 = 8 * 18 + 6 <= GCF = 6
18 = 3 * 6 + 0

150 & 210
210 = 1 * 150 + 60
150 = 2 * 60 + 30 <= GCF = 30
60 = 2 * 30 + 0

Well, now that we have our 3 GCF's { 6, 6, 30}, we have to pair them!
Pair 1: 6 & 6
Obviously, the GCF is 6.....

Pair 2: 6 & 30
I won't go through with it. I'm sure you can tell it's 6.

So we take those GCFs to be {6,6}. We take the GCF of that pair to be 6, once again obviously.
So the GCF of 12,18,150, and 210 is 6.

What's Your Favorite?

Loading poll. Please Wait...

My Textbook Recommendation

This is the textbook that I learned the Euclidean algorithm from. There were other classes where we were "taught" the same algorithm (taught in quotes because I already knew it, but others didn't.), but I didn't like those textbooks.

The reason why I prefer this one, and started referring back to it in later classes, is because it doesn't focus solely on theory. It does have proofs and other mumbo-jumbo, but it makes sure to have examples using real numbers and various difficulties, while explaining them using normal language.
Loading

Comment Box

Don't be shy. Tell me if the above instructions made sense and what you'd like added.



  • ChiliMath Jan 4, 2012 @ 11:08 am | delete
    Great lens! Prime factorization is one of the topics my kids in Algebra 1 loved. I have also used the textbook by Gilbert and Vanstone in my undergrad.
Show All

by

TeacherCaren

Welcome to TeacherCaren's squidoo lensmaster page. Since I would like to become a teacher, and will probably go for a teaching fellowship as soon as I... more »

Feeling creative? Create a Lens!

Explore related pages

Related Tags