## Friday, September 20, 2013

### Finding GCF using Prime Factorization

You have lots of experience finding the greatest common factor with various methods (u-turn, listing, rainbow).  However, the most efficient way to find the GCF for any two or more numbers, especially large numbers, is to use prime factorization.  Remember, the prime factor string for any number is unique.  Breaking numbers down into their basic prime factors allows us to manipulate them in ways that help us do things like find GCF and LCM of numbers.  For those of us that stress over simplifying large fractions, prime factorization is invaluable.  See below.

Notice only the COMMON primes between the two numbers are highlight in red.  When you multiply these common primes together you get a product of 72.  This is the greatest factor that is shared among the two numbers.  You may also notice that 12 is a common factor because the prime factor string 2 x 2 x 2 x 3 is found within both of the factor strings of 144 and 1080.  Can you find more common factors of these two number just by looking at their prime factor strings?

Hopefully, you're thinking to yourself why would we need to know this.  Look at the image below.  You can use prime factorization to simply fractions with large numerators and denominators instead of painstakingly using divisibility rules and dividing!

For those of you who want to go deeper, you can find the GCF for any number of numbers.  You just need to make sure each number shares the common primes. Look!

If you need a refresher with prime factorization watch this video.