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:
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)
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)
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
Then, we apply the same process to our remainder 12 along with our B 36 to get:
36 = 24*1 + 12
Then, we take our new remainder 12 along with our new B 24 to get:
24 = 12*2 + 0
And so on, always taking our new B and our new R, as our new A and our new B.
Here's the theorem: At the stage where the remainder is 0, we know that our B, here 12, is the greatest common factor of our original two numbers. This process can take many more steps depending on your numbers, but it always gives the greatest common factor.
As abstract as this sounds, this is actually an idea that is so fundamental to the study of number theory. It even serves as a foundation to prove the Fundamental Theorem of Arithmetic from part one, which is the fact that every number has a unique prime factorization, which we have been relying on for this whole article! Many mathematicians also define division from the Euclidean Algorithm, rather than the other way around, so it represents the backdrop of arithmetic itself as well.
This discussion simply wouldn't be complete without this, and I'm sure you'll see it pop up as you continue to conquer your math journey, especially in finding something called "multiplicative inverses" in modular arithmetic, if that means anything to you.
If you want to learn even more about the algorithm and all of its properties, visit this link: https://sites.math.rutgers.edu/~greenfie/gs2004/euclid.html
If this is something you're intrigued by, definitely feel free to email me or leave a comment, and I'd love to have a full discussion about the Euclidean Algorithm or anything at all from number theory! This concept certainly seemed foreign to me when I began, but give it time and you'll start to have some incredible 'aha' moments. :)
Finding the Sum and Product of the Factors
Now onto a new topic!
First, let's discuss how to find the product of the factors of a number. This is relatively straightforward: all you got to do is pair them up!
For 240, we have the following factors: 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 16, 20, 24, 30, 40, 48, 60, 80, 120, 240, and we can pair them up so that each pair multiplies to 240:
240 = 1*240, 2*120, 3*80, 4*60, 5*48, 6*40, 8*30, 10*24, 12*20, 15*16
Every factor comes with a counterpart that together multiply to the overall number, so this idea works in general for any number with an even number of factors.
We thus have the following formula for the product of the factors: N^(# of factors/2), where you find the number of factors in the way we explained earlier in part one.
This formula does also hold for numbers that have an odd number of factors! All numbers that have an odd number of factors are squares (see if you can explain why, it has something to do with both the number of factors formula and all the exponents being even!), and our product of the factors formula gives an extra fractional 1/2 power that represents a square root. Here's an example.
36 has the following 9 factors: 1, 2, 3, 4, 6, 9, 12, 18, 36.
We can pair up most of them: 36 = 1*36, 2*18, 3*12, 4*9, and we're left with the square root: 6.
To apply the formula, we take 36^(9/2). Notice that this breaks down to (36^4)*(36^(1/2)), which is simply the product of the four pairs with one extra half-power. A half-power is just a square root, so this reduces to (36^4)*6, which is exactly the product of the factors that we wanted: four pairs of 36, and one additional 6. Thus, we've confirmed how to find the product of the factors for any number, as long as we know how to calculate its number of factors, which comes from part one.
Finally, here's how to find the sum of the factors.
Let's use 36 as our example. We'll not only list the nine factors, but also the prime factorizations of those nine factors:
36's factors: 1, 2, 3, 4, 6, 9, 12, 18, 36
Prime factorizations of 36's factors: (2^0)*(3^0), (2^1)*(3^0), (2^0)*(3^1), (2^2)*(3^0), (2^1)*(3^1), (2^0)*(3^2), (2^2)*(3^1), (2^1)*(3^2), (2^2)*(3^2)
From all of our previous discussions, you should notice that this covers every possible combination with exponents less than or equal to those of 36. With all this symmetry involved, it might not be too surprising that there is a possibility for some sort of expansion here.
Look at this expression:
(2^0 + 2^1 + 2^2)(3^0 + 3^1 + 3^2)
When you "FOIL" it out to get all the individual terms, you'll notice that it simply becomes:
(2^0)*(3^0) + (2^1)*(3^0) + (2^2)*(3^0)+ (2^0)*(3^1) + (2^1)*(3^1) + (2^2)*(3^1) + (2^0)*(3^2) + (2^1)*(3^2) + (2^2)*(3^2) = 1 + 2 + 4 + 3 + 6 + 12 + 9 + 18 + 36 = 1 + 2 + 3 + 4 + 6 + 9 + 12 + 18 + 36.
Even though the factors are rearranged, it should be pretty clear that our expansion both involves every single factor (and each involved term is a factor) and sums them up all for us! Thus, instead of completing an overly long sum, we can simply do a multiplication.
(2^0 + 2^1 + 2^2) = 1 + 2 + 4 = 7
(3^0 + 3^1 + 3^2) = 1 + 3 + 9 = 13
Then, the sum of the factors of 36 is simply 7*13 = 91.
If you want, feel free to verify that our long sum also gives 91.
In general, once we prime factorize our number, we take each prime power and add up all the powers of that prime less than or equal to our given power, creating a term. Then, we repeat for each prime, creating a term of summed-up powers for every prime power in our prime factorization. Finally, we multiply the terms together.
I'll leave the details to you; you have all the tools to make sure our expansion accounts for all the factors (and includes no numbers that aren't factors) and sums them up the way we should. Just rely on our critical fact: each power/exponent of a factor of N must be less than or equal to the corresponding exponent in the prime factorization of N, and vice versa, if this condition is true for a number, that number must be a factor of N.
For now, I'll show you one more example to drill this idea into your brain. Let's find the sum of the factors of 630 = 2*(3^2)*5*7.
That would be (2^0 + 2^1)*(3^0 + 3^1 + 3^2)*(5^0 + 5^1)*(7^0 + 7^1) = (1+2)*(1+3+9)*(1+5)*(1+7) = 3*13*6*8 = 1872
This one can be quite the party trick! Ask a friend to find the sum of the factors of some big number with small prime factors (that they choose) as quickly as they can with a calculator, while you simply multiply a couple of easy quantities in your head, beating them at their own game.
Now it's your turn! Here are some example problems.
What is the sum and product of the factors of 2020?
A positive integer n is nice if there is a positive integer m with exactly four positive divisors (including 1 and m) such that the sum of the four divisors is equal to n. How many numbers in the set {2010, 2011, 2012, ... , 2019} are nice? (2013 AMC 10B Problem 24)
If the product of the factors of n is 2^36, what is n? Can you expand this idea? What is the product of the factors of 2^k in terms of the kth triangular number?
We're at the end of the content for this article! The best number theory topics for you to learn for the AMC from here are number bases, divisibility rules, modular arithmetic, Fermat's Little Theorem, and Euler's Theorem, and if requested, I'd definitely enjoy writing an article about any of them! For now, check out some of the resources in the summary below.
SUMMARY
Here's a summary of this two-part series! I'm keeping these explanations in words because to me, having the fundamental understanding in terms of words and ideas of what you're doing is way more valuable than memorizing formulas. You're welcome to look up the formulas for these concepts yourself if you'd like.
To find the number of factors, take the exponents in the prime factorization, add one to each, and multiply the results.
To find the number of odd factors, take all the exponents in the prime factorization except the exponent of 2, add one to each, and multiply the result.
To find the number of even factors, take all the exponents in the prime factorization except the exponent of 2, add one to each, and multiply all of the results with the exponent of 2 (in short, do not add one to the exponent of 2). You may also subtract the number of odd factors from the number of factors.
To test if a number is an nth power, make sure all the exponents in its prime factorization are multiples of n. You can use this idea to find the number of square, cube or nth power factors of a given number.
To find the greatest common factor of two (or more) numbers, multiply the minimum powers of each prime in the factorizations of the numbers.
To find the least common multiple of two (or more) numbers, multiply the maximum powers of each prime in the factorizations of the numbers.
To find the product of the factors, raise your given number to the power of the number of factors divided by 2.
To find the sum of the factors, for each prime in the factorization, add up all the powers of the prime less than or equal to the power of that prime in the factorization to create a term. Then, multiply all the terms.
I'll also throw in some additional practice problems here that reference the material from both part one and part two:
The number 21! = 51, 090, 942, 171, 709, 440, 000 has over 60,000 positive integer divisors. One of them is chosen at random. What is the probability that it is odd? (2017 AMC 10B Problem 20)
How many perfect squares are divisors of the product 1! * 2! * 3! * 4! * 5! * 6! * 7! * 8! * 9!? (2003 AMC 12A Problem 23)
Given positive integers a, b, c, d such that a^3 = b^2, c^3 = d^2 and c - a = 25, determine a, b, c, d. (Berkeley Math Circle)
Find all positive integers n such that 2^8 + 2^11 + 2^n is a perfect square. (Berkeley Math Circle)
Maya lists all the positive divisors of 2010^2. She then randomly selects two distinct divisors from the list. Find the probability that exactly one of the selected divisors is a perfect square. (2010 AIME I Problem 1)
If the GCD of A and B is 7 and the LCM is 63 and A > B, what is the value of A? (Pilinguals)
The only prime factors of an integer n are 2 and 3. If the sum of the divisors of n (including n itself) is 1815, find n. (PUMaC)
Here are some great resources to find more problems:
http://www.pilinguals.org/uploads/1/2/0/9/120937897/lvl1_week_1_notes_1.pdf
https://www.cheenta.com/amc-8-number-theory-questions-year-wise/ (AMC 8 Number Theory Problems)
https://artofproblemsolving.com/wiki/index.php/Category:Introductory_Number_Theory_Problems (Introductory Number Theory AMC 10/12, AIME Problems)
https://artofproblemsolving.com/wiki/index.php/Category:Intermediate_Number_Theory_Problems (Intermediate Number Theory AMC 10/12, AIME Problems)
From a content perspective, I also highly recommend these resources:
CONCLUSION
That's it! Hopefully, that was a helpful guide, and now I'll follow it up with a conclusion.
We've already explored prime numbers at length through my previous two-part series on prime numbers: Why Are Primes So Fascinating? and The Search for the Largest Primes. Looking at the sequence 2,3,5,7,11,13,17,19... you may have noticed it appears fairly random in the way the primes are placed, and one of the main topics we looked at in my previous two-part series is this "random" quality of the prime numbers—how a sequence so fundamental can be so dangerously mysterious.
In the first article, we explored not only what primes are, but also why they appear to get rarer as the sequence gets larger, how to find them with a sieve, and how cicadas are intrinsically related! In the second, we discussed the modern research on primes: how computers look for prime numbers with millions of digits, why prime numbers are so important to our modern-day security system, and even a million-dollar problem, the Riemann Hypothesis, that mathematicians still cannot solve.
These are some of my favorite articles I've ever written for GLeaM, so I highly recommend reading them to broaden your understanding of primes—and to comprehend their mystery as well as their factorizations.
I absolutely love discussing number theory, so just let me know if you'd like another more advanced article in the field. I'm also totally willing to discuss other math competition-related concepts in other subjects, including algebra, combinatorics, and geometry, so feel free to request an article about one of those as well.
See you for the next article!
Comments