Number Theory 101: From the Basics of Prime Factorizations to Acing the AMC

Updated: Dec 16, 2020

Welcome back! Today, I'll give you an introduction to one of my favorite subjects in math, number theory, and we'll discuss why it's so important.


This article will be in two parts with the second part going up later this month. It will be geared to a beginner and intermediate level, so it should be accessible regardless of your background knowledge. For those who consider themselves advanced, this could also serve as a helpful review and overview, so you should enjoy this as well!


All of these topics are extremely applicable to math competitions (they make up a sizable portion of the AMC competitions), but I think you'll find this article both interesting and relevant wherever you find yourself on your math journey, whether you're a veteran or you just want to discover what the wider world of math is all about!


Number theory is, of course, the study of numbers, but for the most part, it deals particularly with positive integers (meaning, the counting numbers: 1, 2, 3, 4...), and their relationship with what are called prime numbers. Number theory covers a wide range of topics, but in this article, we'll focus specifically on prime factorizations—and all the wonderful questions you can answer by using them in the right way.


If you've read the two-part GLeaM series on primes (part 1 and part 2), you can even consider this a second two-part series to that series. I'd highly recommend you check those two articles out as well, but this series does stand entirely alone and I'll give lots of explanation along the way.


I've explained a lot throughout to make sure we all understand every concept introduced throughout here (and you'll gain a lot from reading the whole thing!), but definitely feel free to skip through and read only the parts you don't already understand. I've left lots of problems throughout to check your understanding as well.


What is a Prime Factorization?

We first must introduce the concept of divisibility: a number is divisible by another number if and only if you can multiply the second number by some positive integer to get the first. For example, 6 is divisible by 3, because you can multiply 3 by the positive integer 2 to get 6 (or to say it another way, because 3*2=6), and 20 is divisible by 4 because 4*5 = 20.


We call all numbers that a given number is divisible by its factors. 6 is divisible by 1, 2, 3, and 6, so its factors are 1, 2, 3, and 6. You'll sometimes also see the word divisor used to mean the same thing.


A prime number, then, is any number which only has 2 factors: 1 and itself.


It might be fairly easy to see that 2 or 3 is prime, because any potential factor must be smaller than 2 or 3, and we can tell that the only factors of 2 and 3 are 1 and themselves by simply examining the numbers smaller than them.


In general, one way to tell if a number x is prime to test every single number less than x and greater than 1, and make sure none of them are factors of x. For example, we know 5 is prime because it is not divisible by 2, 3, or 4.


(In fact, it is actually enough to only test every number up to the square root of x to make sure x is prime. See if you can explain why!)


Listing the first several prime numbers gives us 2,3,5,7,11,13,17,19,23... This is the sequence of prime numbers.


With those definitions out of the way, let's look at a statement that is so important it is called the Fundamental Theorem of Arithmetic: Every integer has a unique prime factorization.


It turns out that we can use prime numbers as building blocks. When we factorize an integer, we break it up into a product of primes. For example, we could factorize 6 as 2*3, 18 as 2*3*3 = 2*(3^2), or 80 as 2*2*2*2*5 = (2^4)*5. (Here, the ^ symbol just means "to the power of"; 3^2 is 3 squared.)


All the Fundamental Theorem of Arithmetic means, is that there is only one way to break each number up into a product of primes, up to rearrangement. If 6 is 2*3, there are no other primes we could find that multiply to 6, other than 3*2 of course, but that is simply a rearrangement of 2*3. We can never find another set of primes that multiply to 6.


Regardless of whether this seems obvious to you, this statement is actually far from intuitive, and it takes quite a lot of math to show that it is always true. The good news is we do know that it's true, so feel free to use it as much as you want!


We often find prime factorizations using a factor tree as a visual aid, essentially dividing out one prime at a time until all we're left with is primes, and because of the Fundamental Theorem of Arithmetic, it doesn't matter what prime we divide out first or which pair of factors we start at.

Photo courtesy of Sarthaks eConnect.

Using this theorem, we'll construct some helpful facts used throughout number theory and also math competitions, and we'll see just how valuable and fundamental primes are.


Counting the Number of Factors

Any number that is not prime is called composite. The interesting thing about composite numbers is they often have lots of prime factors, which give them many different possible factors.


Let's pick the number 240 for the sake of this demonstration. The prime factorization of 240 is (2^4)*3*5.


The number 240 has 20 factors: 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 30, 24, 40, 48, 60, 80, 120, 240. Notice that every single one of these factors has a prime factorization that only contains the primes 2, 3, and 5, just like 240, and moreover, these prime factorizations are just part of the factorization of 240: each power/exponent must be less than or equal to the corresponding exponent in the prime factorization.


(For example, 60 is (2^2)*(3^1)*(5^1) while 240 is (2^4)*(3^1)*(5^1), and each exponent for 60 on the 2, 3, and 5 is less than or equal to that of the 240.)


If you need help seeing this last statement, let's look at the number 32 = 2^5. 32 is not a factor of 240, and it also contains a power of 2 that is greater than the power of 2 that 240 contains: 2^5 > 2^4. This creates a problem because this 2^5 does not divide evenly into the 2^4 portion of 240, because it is too large, and it can't divide into any other primes in the factorization of 240 either—because they're separate quantities from the power of 2. Thus, 32 cannot be a factor of 240. In general, all factors of a number must contain only primes with exponents up to the exponent in the prime factorization of the original number (and in the other direction, if a number contains only primes with exponents up to the exponent in the prime factorization of the original number, it's a factor of the original number.)


This small observation allows us to make a rather important discovery: how to find the number of total factors of a number. For 240, we know every factor has a power of 2 between 2^0 (this represents no powers of 2, 2^0 is just equal to 1) and 2^4, a power of 3 between 3^0 and 3^1, and a power of 5 between 5^0 and 5^1.


To count the number of factors of 240, we just have to pick one of the 5 possible powers of 2 (2^0, 2^1, 2^2, 2^3, 2^4), one of the 2 possible powers of 3 (3^0, 3^1) and one of the 2 possible powers of 5 (5^0, 5^1). To count the total number of factors, all we do is multiply these possibilities: 5*2*2 = 20, which is exactly the number we found when we counted them directly.


In general, to find the number of prime factors of a number with a given prime factorization, you just have to add 1 to each of the exponents in the prime factorization (counting all the possible powers of a given prime for a factor, including the zeroth power!) and multiply all those quantities.


It's completely fascinating how easy this answer is to obtain. Check out this example!

Courtesy of WikiHow

Now, how do we use this idea to count something more specific, like the number of odd factors of a given number? Or the number of even factors?


All it takes is the observation that any odd number can have no power of 2 in its prime factorization (so any odd factor must have 2^0 as its power of 2), while any even number must have a power of 2 greater than 2^0 in its factorization, to make sure it is divisible by 2 and is not odd.