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

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 week. 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.


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.


For the number of odd factors, we go about a similar process, except we choose the 1 possible power of 2 (2^0), 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), for a total of 1*2*2 = 4 odd factors.


Notice that since we're essentially disregarding the power of 2 by just using 2^0, we're also in a sense finding the number of factors of the largest odd factor of our number, which for 240 happens to be 15. 15 has 4 odd factors, and these become the 4 odd factors of 240.


For the number of even factors, we choose one of the 4 possible non-zero powers of 2 (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), for a total of 4*2*2 = 16 even factors.


Of course, we could also find the total number of factors and subtract the number of odd factors to get the number of even factors, which essentially is subtracting the number of factors of 15 from the number of factors of 240. Here, that gives 20-4 = 16.


In math competitions, the questions you're asked aren't as straightforward as "how many factors does 240 have?" but they're often based on the same ideas. Here are a few examples to try:

  1. What is the sum of all the three-digit multiples of 11 which have exactly 10 factors?

  2. What is the least positive odd number that has exactly 18 factors?

  3. Let n be the smallest positive integer that is a multiple of 75 and has exactly 75 positive integral divisors, including 1 and itself. Find n/75. (1990 AIME Problem 5)

Notice that these simply add extra conditions to the problem of finding the number of factors. A multiple of 11 must have an 11 in its prime factorization and a multiple of 75 must have at least (5^2)*3 somewhere in its factorization.


Also, rather than counting factors of a given number, in many situations, you must find one or several numbers with the given number of factors. For example, to find a number with eight factors, you might pick two numbers that multiply to 8, say 4 and 2, and construct a number such that finding its number of factors is essentially multiplying 4 and 2. This would correspond to the factorization (p^3)*(q^1) where p and q are any primes.

Specifically, 24 could work because it is (2^3)*(3^1), and by taking all the exponents, adding one, and multiplying, we end up with 4*2=8, ahd 8 is its number of factors.


I'll go ahead and tell you that to get 8 factors, the three possible factorization structures are p*q*r, (p^3)*q and p^7 for some prime p, q and r, but how do we know that? And how can we be sure in general that we've considered all possible structures for a desired number of factors? These are great questions to consider while you try your hand at the problems above, and I think you'll gain a lot more if I let you try them yourselves!


Feel free to discuss the answers to these questions in the comments, or to contact me directly!


What else can you do with a prime factorization? Squares and Cubes


Here's something interesting. How can we tell if a number is a square or a cube from its prime factorization?


It's a pretty easy test: if all the exponents in a number's prime factorization are even, it's a square. For example, the number 144 = 2^4*3^2 can be rewritten as (2^2*3)^2 because all of the exponents are even, a property that allows us to simply factor out a 2 from all the exponents. As a bonus, this allows us to find 144's square root, which in this case is just (2^2)*3 = 12.


For a cube, we must simply test if all the exponents of a number's prime factorization are multiples of 3, and for a general nth power, we must test if all the exponents are multiples of n.


Now, we can consider how to find the number of square factors a given number has. We'll perform a similar process to what we did above with total number of factors, but we'll only consider the even exponents. For 240, we have three possible powers of 2 (which must both be even and less than or equal to 2^4), 2^0, 2^2, 2^4, one possible power of 3, 3^0, and one possible power of 5, 5^0. This comes to a total of 3*1*1 = 3 square factors, which here happen to be 1, 4 and 16.


Here are a few example problems to try out:

  1. How many square factors does 1080 have?

  2. What is the square root of 3*7! - 6*5! Hint: Factor out 5! from 7!

  3. What is the sum of the exponents of the prime factors of the square root of the largest perfect square that divides 12!? (2013 AMC 12B Problem 9)

Note: This is as good of a time as any to introduce the concept of a factorial, denoted by an exclamation mark. To find the factorial of a number, you just multiply that number and all the positive integers less than it. For example, 3! = 3*2*1 = 6, and 6! = 6*5*4*3*2*1 = 720.


Often, you'll see them come up in number theory problems, and all you'll have to do is write out the entire factorial as a product (as I've shown above) and factorize from there to write the prime factorizations. There is a trick to finding the prime factorizations known as Legendre's formula, but I'll leave that to you to look up if you're interested.


CONCLUSION

That's it for today's article! In part two, we'll explore a few more interesting and advanced concepts, including greatest common factors, least common multiples, the sum of the factors of a given number and more! The second article will build on this one, and it will be going up on Sunday, so make sure you check back for it!


Here is one last point I'd like to make: Keep asking questions!


Even in this article, there are so many more concepts we could explore. There are some ideas we assumed to be true because they made sense and we didn't feel the need to explore them further, but we always need to consider why every step we take is true. Why do we know that the potential factors of a number must be less than that number? Why is the Fundamental Theorem of Arithmetic true? I'd love to discuss some of these questions with you in the forums or comments, but either way, it's important to understand that number theory has an incredible level of depth that is worth looking further into, and this is just one way of approaching the wide range of the subject.


That's it! See you for part two!


Cover image courtesy of Science News