GRE Prime Factorization and Divisibility Problems
Did you know that you can attend the first session of any of our online or in-person GRE courses absolutely free? We’re not kidding! Check out our upcoming courses here.
Here’s a hard problem that I used to teach in session 1 of our GRE course (my poor students! This was a rough intro to GRE math.)
If you’d like to, give yourself a minute or two to try this (but don’t bang your head against it for too long). If you’re thinking wow, I have no idea what’s going on here—well, it’s a good thing you’re reading this. And even if you do feel comfortable with this problem, it might be worth reading further to see how the techniques used to solve this are more broadly applicable in GRE Quant.
Divisibility problems like this one crop up fairly regularly on the GRE. They might ask you what number could be a factor of another number, or what the least common multiple of two numbers is. Often, they throw variables into the mix to make it trickier. Some terms to watch out for that signal you’re in a divisibility problem are:
- Factor
- Multiple
- Divisible by
- Divides evenly into
- Remainder
- Greatest common factor
- Least common multiple
Prime factorization is one of our best tools for working with divisibility—so as soon as I spot this kind of language, I start thinking about finding prime factorizations of the numbers involved. Even if I’m not sure I know how to solve the problem entirely, I’ll start with prime factoring; it often helps me to understand the problem better.
All numbers can be written as a product of prime factors. For example, 27 breaks down into 33. For larger numbers, I can use a factor tree to help figure out the prime factorization:
Now, why is this helpful? Well, if every number can be broken down into the same small components (prime numbers), this makes it a lot easier to compare numbers. Let’s say I want to know if 432 is divisible by 24—assuming, for the moment, that I don’t have a calculator handy, since, for some of these divisibility problems, a calculator won’t help you.
We know the prime factorization of 432 is 2433. Now, I find the prime factorization of 24: 233. I compare. I’m looking to see if 24 will fit into 432—that means that 432 has to have at least as many 2s and 3s in it as 24 does. And yes, that works! I could also think of this as canceling out the factors when I divide:
The GRE could make this more difficult: they could ask if 432n is divisible by 24n. Well, here, I just treat the variable as another factor, like 2 or 3. So it still cancels out, i.e. 432n is divisible by 24n.
Now, what if instead I was looking for the least common multiple of 81 and 432? I know that 81 x 432 (which equals 34,992) will be one common multiple, but it might not be the smallest one. Here prime factorization can help again. Remember that 432 = 2433. And 81 = 34. The least common multiple has to have just enough prime factors to cover both numbers. So it has to have four 2s (to cover all the 2s in 432) and four 3s (this covers both the three 3s in 432 and the four 3s in 81). Remember that the least common multiple doesn’t have to be divisible by both AT THE SAME TIME—just by each individually; that’s why I don’t need seven 3s. So 2434 = 1296. That’s my least common multiple—way less than 34,992!
Now that we’re starting to see the power of prime factorization, let’s apply that to our original problem:
Phew, there’s a lot of math jargon here! Greatest integer value, such that, n, factor. Argh. But I see that word “factor,” so I’m just going to dive in with some prime factorization and see if that helps me unravel the problem. Now, I’m not quite sure about 2006, so I’ll just start with 200. That has a prime factorization of 2352. Okay. So let me plug that in for 200—(2352)6. If I’m up on my exponent rules (which, hopefully, I am), then I know to distribute that “6” to each of the exponents inside the parentheses, and to multiply those exponents together, since I’m raising a power to a power. That gives me 218512.
Now that I’ve done this, the problem is starting to make sense to me. My prime factorization of 2006 has eighteen 2s in it. So I can have up to eighteen 2s in any factor of 2006. Oh! And now I see—all the stuff about 2n? That’s just a fancy way of asking how many 2s can go into 2006. So I put in my answer—18—and I’m done.
Prime factorization is pretty useful, and, for divisibility problems, often a great place to start. There’s a larger lesson here too, though, about solving tricky word problems. A lot of times, we read difficult word problems and immediately throw up our hands—what on earth is going on here? When this happens, I take a deep breath and slow down. I focus on what I DO know about the problem, rather than on what is confusing. And I use that knowledge as an anchor—it gives me some clue about what technique or strategy I might start applying, keeping in mind that doing a little work on one part of the problem will likely help me to figure out the part that’s tripping me up. Here, I used the word “factor” as a clue; it told me to start with prime factorization. And once I’d done that, the problem came into focus, and I was able to understand better what I was looking for and how to get there. ?
Want more guidance from our GRE gurus? You can attend the first session of any of our online or in-person GRE courses absolutely free! We’re not kidding. Check out our upcoming courses here.
Cat Powell
is a Manhattan Prep instructor based in New York, NY. She spent her undergraduate years at Harvard studying music and English and is now pursuing an MFA in fiction writing at Columbia University. Her affinity for standardized tests led her to a 169Q/170V score on the GRE. Check out Cat’s upcoming GRE courses here.