Number of Factors of a Large Integer

January 25, 2008

Occasionally a GMAT question will ask you for the number of factors of a certain integer. Usually that integer will be large (441 is the object of one question that comes to mind), since the question wouldn't be very challenging otherwise.

For a long time, I did exercises like that the old-fashioned way: starting with 1, finding all the numbers along the way that were divisible by 441. It can be helpful to use a prime factorization, but even with that assistance, the job requires some brute force.

No longer.

The method I'm about to show you isn't for the math-averse; it introduces permutations into a question type that doesn't need them, so unless you're comfortable with the idea of factors and you aren't confused by permutations, this should help you.

Find the Number of Factors

The concept behind this method is that the prime factorization of a number determines all of its factors. If a number is divisible by 2, for instance, 2 will be a factor of many of the number's factors. In fact, each factor of a number is built up of one or more of the number's other factors.

Take 18, for instance. The prime factors of 18 are 2 and 3; the prime factorization is 2 times 3 times 3, or (2^1)(3^2).

Consider each of 18's factors in terms of its own prime factorization:

• 1 = (2^0)(3^0)
• 2 = (2^1)(3^0)
• 3 = (2^0)(3^1)
• 6 = (2^1)(3^1)
• 9 = (2^0)(3^2)
• 18 = (2^1)(3^2)

If you look at all of those numbers in terms of their factorizations, you'll see every possible arrangement of 2 to the 0 or 1 power with 3 to the 0, 1, or 2 power. That's no accident.

To generalize that method, here's your approach:

1. Find the prime factorization of a number (each one of the number's prime factors raised to the appropriate power).
2. List all of the exponents.
3. Add one to each of the exponents. (Remember, it's possible to raise the prime factor to the zero power.)
4. Multiply the resulting numbers.

Find the Number of Factors of 196

Let's try those steps with 196. I've never seen a specific GMAT question asking for the number of factors of 196, but it's exactly the sort of number they are likely to use.

1. The prime factorization: 196 = (2^2)(7^2)
2. The powers: 2 and 2
3. Add one to the powers: 3 and 3
4. Multiply the results: (3)(3) = 9

There are 9 factors of 196. To see what those are, work through the permutations of the exponents 0, 1, and 2 for the prime factors 2 and 7:

• (2^0)(7^0) = 1
• (2^1)(7^0) = 2
• (2^2)(7^0) = 4
• (2^0)(7^1) = 7
• (2^1)(7^1) = 14
• (2^2)(7^1) = 28
• (2^0)(7^2) = 49
• (2^1)(7^2) = 98
• (2^2)(7^2) = 196

I can't imagine a GMAT question on which you'll need to figure out what all the factors are, but it's nice to see that the method works. This is the sort of technique that should be very far down your list: It's just not that high of a priority. But for those of you attempting to add 20 or 30 points to an already high score, it's a handy time-saving method.

About the author: Jeff Sackmann is a GMAT tutor based in New York City. He has created many resources for GMAT preparation, including the popular Total GMAT Math and Total GMAT Verbal, as well as 1,800 practice GMAT math questions.

• Older: GMAT Reading Comprehension (Beginner's Guide)
• Newer: GMAT Sentence Correction (Beginner's Guide)
• General GMAT Math: more articles
• All articles at GMAT HACKS