# Manhattan GMAT Challenge Problem of the Week – 25 May 2010:

by on May 25th, 2010

Here’s the latest Challenge Problem! As always, the problem and solution below were written by one of our fantastic instructors. Each challenge problem represents a 700+ level question. If you are up for the challenge, however, set your timer for 2 mins and go!

## Question:

The smallest prime factor of 899 is x. Which of the following is true of x?

a. 1 < x ≤ 7
b. 7 < x ≤ 14
c. 14 < x ≤ 21
d. 21 < x ≤ 28
e. 28 < x ≤ 35

One path to the solution involves brute force. We can test primes in order of size, applying divisibility rules that we know for small numbers, such as 3. However, all the simple rules fail. This method may wind up being the quickest way, but it is laborious.

The shortcut in this problem involves wishful thinking. 899 is awfully close to a nice number: 900. The reason 900 is so nice is that it is a square: = 900. (By the way, since we know from the wording of the problem that 899 has a prime factor less than itself, at least one of the prime factors must be below the square root of 899, and at least one prime factor must be larger than the square root of 899. This square root is just under 30. This is another reason why we might think of the nearby perfect square, 900.)

So we can write 899 = 900 – 1 = – 1.

Now, ideally we would notice that we can take one step further and rewrite – 1 as , since 1 = . Why would we do this? Because now we have written 899 as a difference of squares, which we should know how to factor:

899 = 900 – 1 = – 1 = = (30 + 1)(30 – 1) = 31 × 29.

Both 31 and 29 are prime numbers. The smallest prime factor of 899, therefore, is 29.

Special Announcement: If you like the explanations we give for our Challenge Problems, try our new Official Guide Companion , available now. It has detailed answer explanations to every quant question in the Official Guide.

• Good question! Now I know how to do it in 30 seconds.
Thank you!

• Nice reply. But, I am confused about one thing: if you can break a number with (a square - b square) ; does it mean (a-b) will always be the smallest prime number. 29 would be a prime factor ; that's true but how could you draw the conclusion in this way that 29 would be the smallest one. It would be great if you can explain this.

• Good question, Rittick. No, the rule you tried to derive is not ALWAYS true - you need to take it a little further than that. What you're trying to do is break the number down into all of its prime factors. Once you do that, then you can tell which is the smallest prime factor.

When you find 2 numbers that multiply to give you your desired number, then you can use those factors to figure out ALL of the prime factors of your desired number. This might be easier to understand if we choose a smaller number as an example. Let's choose 24.

Two factors of 24 are 6 and 4. 6 x 4 = 24. 6 and 4 can be further broken down into smaller primes. 6 = 2x3. 4 = 2x2. 2 can't be broken down any further; neither can 3. So, if we break 24 down into all of its prime factors, we get 2x3x2x2. Once we've broken a number down into its prime factors, we can figure out which one is the smallest one. (2 in this example.)

In the above problem, the two solutions to the quadratic are 29 and 31. So 29 x 31 = 899. If we want to know ALL of the prime factors of 899, we try to break down the numbers until we can't go any further, just like we did with 6 and 4, above.

29 and 31 can't be broken into any smaller primes (by definition, because they're already primes themselves, right?). So that's it: 29 and 31 are the only prime factors of 899. 29, therefore, is the smallest one.

• Thanks for the explanation. Can you pls explain this line below again? thanks.

" at least one of the prime factors must be below the square root of 899, and at least one prime factor must be larger than the square root of 899."

• Sure. Prime factors are, by definition, integers. 899 is either a prime itself, or it has other prime numbers as factors (numbers that are smaller than 899, of course!). (In this case, we know that 899 must have other prime numbers as factors, because the problem says that the smallest prime factor of 899 is x, and then the answer choices only include numbers that are smaller than 899.)

IF 899 is a perfect square (it isn't), then we can find the prime factors of the number.

For example, 25 is a perfect square. The square root of 25 is 5. 5 is one prime factor of 25. 5 can't be broken down any further, so 5 is the only prime factor of 25.

For example, 16 is a perfect square. The squre root of 16 is 4. 4 is a factor of 16, but it's not a prime factor because 4 is not a prime. We can break 4 down into 2x2, though, and we can't break that down any further, so 2 is a prime factor of 16, and it's also the only prime factor of 16 (because we only get 2s when we break the factors down).

899 is not a perfect square, though. So, if we were able to get the square root easily (without a calculator), then by definition, one factor would have to be smaller and the other factor would have to be larger. You couldn't have ONLY two factors that are BOTH larger than the square root - when you multiplied them together, the resulting number would be greater than 899. Nor could you have ONLY two factors that are BOTH smaller than the square root - this time, the resulting product would be smaller than 899.

If you're not sure about what I just typed above, try it out with some smaller numbers, say 24 and 35.