How to Factor Numbers

by Jason Marshall

There are many things in the world of math that seem perfectly interesting but perhaps not particularly important in the grand scheme of things. Occasionally that impression turns out to be true, but sometimes it’s dead wrong. Take for instance the seemingly simple task of factoring numbers. While I’m happy to admit that it’s in no way obvious that this curious bit of math you learned in elementary school is in reality a crucial part of modern life, but it’s nonetheless true.

Want to know how and why? We’ll get there, but we first need to figure out what factoring is, what prime factoring is, and how to actually perform a prime factorization. Then, and only then, will we truly understand and appreciate why factoring numbers is so important in the modern world. Sound like an interesting story? It is. And it’s exactly the story I’ll be telling today.

What Are Factors?

To understand factorization and how to factor numbers we need to know what factors are. Thankfully, the idea is simple: The factors of a number are the numbers you multiply together to make that number. For example, since 3×4=12, we say that the pair of numbers 3 and 4 are factors of 12. Of course, 2×6=12 as well, which means that the pair of numbers 2 and 6 are also factors of 12.

But wait, there’s more because it’s also true that 2x2x3=12 (where we’ve simply switched out the 6 from before with 2×3). So the trio of numbers 2,2,and 3 are yet another set of factors of 12. Are any of these sets of factors better than the others? Well, although this last set might not necessarily be better in some absolute universal sense, it’s definitely special. Do you see why?

What Are Prime Factors?

The big difference between the first two sets of factors—3 and 4 as well as 2 and 6—and the final set of factors—2, 2, and 3—is that the latter set contains only prime numbers. As you’ll recall from our episode on prime and composite numbers, a prime number is any number that is only evenly divisible by itself and the number 1. Since the numbers 2 and 3 are therefore both prime, the set of factors 2, 2, and 3 are what we call the prime factors of the number 12.

Every positive integer has a unique set of prime factors. This is actually a really big deal in the world of math since it means that every single one of the infinite number of positive integers can be broken apart and then recreated by multiplying together a unique set of prime number “building blocks.” For the number 12 those building blocks are the prime numbers 2, 2, and 3; as you can check yourself for the number 15 those building blocks are the prime numbers 3 and 5; and for the number 17 those building blocks are…well…just 17 since it’s already a prime number!

This idea that every positive integer has a unique set of prime factors is such a big deal in math that it has an appropriately “big deal” sounding name: The Fundamental Theorem of Arithmetic.

How to Perform a Prime Factorization

Now that we know what a prime factorization is, it’s time to figure out how to actually carry one out. I like to start by writing the number you’re trying to factor on a piece of paper. Beneath this number draw two downward-pointing arrows and then write the first two factors at the tips of the arrows. How do you know what those first two factors should be? Well, one way to get started is to check to see if the number you’re factoring is an even number. If it is, it must be divisible by 2. Which means that one of your factors is 2 and that you can find the other factor by dividing the original number by 2.

Okay, are we done? Well, if this second factor happens to be prime, then yes. If it’s not, then no. In which case you need to draw another pair of arrows emerging from it and repeat the process. If the new factor is even, you can again divide it by 2. What if it’s not even? Well, that’s where things get a bit tricky.

My suggestion is to start trying to divide by increasingly larger prime numbers. First check if it’s divisible by 3. If it is, great—you now know that 3 is a prime factor and that you can divide the number by 3 to find the next factor. If it’s not, then try 5, then 7, then 11, and so on. Why don’t you need to try any non-primes? I encourage you to take a minute and see if you can figure that out. If you come up with an answer, send me an email at mathdude@quickanddirtytips.com and let me know!

All that’s left to do now is continue this process of repeatedly breaking apart subsequent factors into smaller and smaller factors. Eventually, when you have nothing but prime factors left, you’re done!

Why Is Factoring Important in the Real World?

You now know everything necessary to factor every positive integer in existence. However, that doesn’t mean you know enough to easily factor every positive integer in existence. In fact, as far as we know, no person or thing in the world can easily factor absolutely any positive integer you throw at them.

For example, what’s the prime factorization of the number 35,184,535,666,823? Uh, unless you possess truly prime magical powers (pun intended), it’d take you a long, long, long time to figure out that this number has exactly two prime factors: 8,388,617 and 4,194,319. A computer could actually solve this problem easily. But what if you instead take two much, much larger prime numbers, multiply them together, and ask a computer to calculate the pair of primes you started with? Could it do it?

For large enough numbers, the answer is most definitely no…at least not in any reasonable amount of time. Which is exactly why this very problem is used as the foundation upon which most of the modern cryptography that we use every day to secure our online transactions and interactions is built. The details of how this all works is somewhat complicated, but it’s also a fascinating story of human ingenuity. And it’s a story that we’ll definitely be returning to in the future.

Wrap Up

Okay, that’s all the math we have time for today. While prime factorization is critical for super important things like cryptography, it turns out to also be super important for a bunch of other things in the wide world of math, too. What sort of things? Check back next week to find out!

In the meantime, remember to become a fan of the Math Dude on Facebook where you’ll find lots of great math posted throughout the week. If you’re on Twitter, please follow me there, too. Finally, please send your math questions my way via Facebook, Twitter, or email at mathdude@quickanddirtytips.com.

Until next time, this is Jason Marshall with The Math Dude’s Quick and Dirty Tips to Make Math Easier. Thanks for reading, math fans!