Search

Number Theory 101: From the Basics of Prime Factorizations To Acing the AMC Part 2

Updated: Dec 16, 2020

It's time for part two! Today, we'll continue our discussion of one of the best subjects in math, number theory, specifically the topic of prime factorizations. We'll see just how fascinating these topics are, and we'll explore their wide and wonderful applications in math competitions.

This article heavily builds on part one, so if the concepts of prime factorization and number of factors are not immediately obvious to you, make sure you check out that article before continuing with this one. Here's the link: https://www.gleammath.com/post/number-theory-part-one

Let's get started!

Greatest Common Factors and Least Common Multiples

First, let me define what a greatest common factor is. Given two (or more) numbers, say 240 and 36, the greatest common factor is the greatest factor that both of them share—the largest integer that divides both.

One way of finding the greatest common factor is to simply list out all the factors of both numbers:

240's factors: 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 30, 24, 40, 48, 60, 80, 120, 240

36's factors: 1, 2, 3, 4, 6, 9, 12, 18, 36

I've bolded the factors they both share, so notice that 12 is the largest one, and hence the greatest common factor.

Of course, this isn't a very efficient method, so we'll see if we can use prime factorizations. Remember in part one, we explained that any factor of a number must have a prime factorization where each prime has an exponent less than or equal to that of the original number. This is also true in the other direction: if that condition is met, the number is a factor.

Thus, if and only if a number is a common factor of two numbers, the exponents on its primes must be less than or equal to those on the corresponding primes in both of the numbers we're considering.

Let's return to our example so I can show you what I mean.

The prime factorization of 36 is (2^2)*(3^2) and the prime factorization of 240 is (2^4)*3*5. Here, the power of 2 must be less than or equal to 2^2, because it is the minimum power of 2 listed here (belonging to 36), the power of 3 must be less than or equal to 3^1 because it is the minimum power of 3 (belonging to 240), and the power of 5 must be less than or equal to 5^0 = 1 (from 36—it's not divisible by 5 at all), which is the default of minimum power of 5.

See how these conditions make our number divide both 36 and 240? By being less than or equal to the minimum power, our power is less than or equal to the exponents in both of the numbers we're considering, so it divides them!

Any common factor must meet these less-than-or-equal conditions, but we must take it one step further to find the greatest common factor, taking the largest possible powers that satisfy the conditions. This corresponds to simply letting it be equal (rather than less than or equal) to that minimum power.

Thus, our power of 2 is 2^2, our power of 3 is 3^1, and our power of 5 is 5^0 for a greatest common factor of (2^2)*3 = 12.

In general, to find the greatest common factor, we must take the minimum power of each prime between our given numbers and multiply the powers together. This is true even when we have more than two numbers.

Now, let's define a similar concept: the least common multiple. Given two (or more) numbers, the least common multiple is the smallest number that is a multiple of both numbers, or in other words, has both given numbers as a factor.

Again, we can solve this by listing (the multiples, this time):

240's multiples: 240, 480, 720, 960, 1200, ...

36's multiples: 36, 72, 108, 144, 180, 216, 252, 288, 324, 360, 396, 432, 468, 504, 540, 576, 612, 648, 684, 720, ...

By the lists, it is clear 720 is the answer, as it is the smallest number in both lists.

However, we can also find the least common multiple from the prime factorizations. Perhaps, it won't surprise you so much when I tell you that it's super similar to our last definition: This time, we take the maximum power of each prime between our given numbers and multiply them together.

Here, the maximum power of 2 is 2^4, the maximum power of 3 is 3^2, and the maximum power of 5 is 5^1, and just as expected, (2^4)*(3^2)*5 = 720

See if you can explain why exactly this is true, based on the ideas we used for the greatest common factor.

I'll give you an outline: Essentially, we need both of the numbers we're considering (here 36 and 240) to have exponents that are less than or equal to our common multiple, which means we must choose an exponent greater than or equal to the maximum exponent between our two numbers. Setting it equal to that maximum exponent gives us the least common multiple. Work through the reasoning yourself and see if you can convince yourself of this fact!

In fact, there is one other interesting thing to notice here. For two numbers, we have this important theorem:

gcf(a,b)*lcm(a,b) = ab

where gcf denotes greatest common factor and lcm denotes least common multiple—because for each prime, one number has the maximum power of that prime and one has the minimum power.

To see this more clearly, take our example where 36 = (2^2)*(3^2) and 240 = (2^4) * 3 * 5.

To form the greatest common factor, we take the smaller exponents: 12 = (2^2)*3.

To form the least common multiple, we take the larger exponents: 720 = (2^4)*(3^2)*5

Thus, we're distributing the same "building blocks" in a slightly different way, with each exponent going to either the greatest common factor or the least common multiple (it doesn't matter which if they're equal!).

Multiplying the same set of "building blocks" gives the same answer, so the product is the same. Here, 36*240 =(2^6)*(3^3)*5 = 8640 = 12*720.

Here are a couple of sample problems:

1. What is the ratio of the least common multiple of 180 and 594 to the greatest common factor of 180 and 594? (2013 AMC 8 Problem 10)

2. What is the largest 3-digit number that is a multiple of 12 and a multiple of 21, but not a multiple of 22? (Pilinguals)

3. If the product of two numbers is 360 and their greatest common factor is 9, what is their least common multiple?

There is one other cornerstone of any number theory discussion about the greatest common factor. Usually, prime factorizations suffice for competitions, but this idea is critical to understanding number theory conceptually (especially when you go into college-level math courses), and it is called the Euclidean Algorithm.

I won't go into too much detail here because I could honestly devote a whole article to this, but the idea is that if you apply a certain algorithmic process to your two numbers, you will get the greatest common factor. Here's the process.

First, you divide your larger number (A) by your smaller number (B), and you write the results as follows: A = B*Q + R, where Q is the quotient and R is the remainder.

For example, 240 divided by 36 gives 6 with a remainder of 24, so we write:

240 = 36*6 + 24