Manhattan GMAT Challenge Problem of the Week – 8 June 2010

by Manhattan Prep, Jun 8, 2010

This is our 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

A Sophie Germain prime is any positive prime number p for which 2p + 1 is also prime. The product of all the possible units digits of Sophie Germain primes greater than 5 is:

a. 3

b. 7

c. 21

d. 27

e. 189

Answer

The first step is to make sure that we truly understand the definition of these special, so-called Sophie Germain primes. The idea is that if both p and 2p + 1 are prime, then p is a Sophie Germain prime. We can quickly test some small primes to see whether they are Sophie Germain primes:

If p = 2, then 2p + 1 = 5, which is also prime. So 2 is a Sophie Germain prime.

If p = 3, then 2p + 1 = 7, which is also prime. So 3 is an SG prime.

If p = 5, then 2p + 1 = 11, which is also prime. So 5 is an SG prime.

If p = 7, then 2p + 1 = 15, which is NOT prime. So 7 is NOT an SG prime.

We are looking for the product of all the possible units digits of SG primes greater than 5.

Lets first narrow down the possible units digits of ALL primes greater than 5. First of all, no prime greater than 2 can end in an even digit (0, 2, 4, 6, 8), since no even number greater than 2 is prime. Likewise, no prime greater than 5 can end in 5, since all integers with a units digit of 5 are divisible by 5. So we can see that primes greater than 5 must end in 1, 3, 7, or 9 (e.g., 11, 13, 17, and 19). The question is whether the SG condition further restricts the possible units digits.

If a prime p ends in 1, then 2p + 1 ends in 3, which is a safe units digit for a prime.

If a prime p ends in 3, then 2p + 1 ends in 7, which is also a safe units digit for a prime.

If a prime p ends in 7, then 2p + 1 ends in 5, which is NOT a safe units digit for a prime greater than 5. So, in fact, no SG prime greater than 5 can end in 7.

Finally, if a prime p ends in 9, then 2p + 1 also ends in 9, which is a safe units digit for a prime.

Thus, SG primes can only end in 1, 3, or 9.

To be rigorous, we should find at least one example of an actual SG prime with each of those units digits, to confirm that we havent missed something.

If p = 11, then 2p + 1 = 23, which is also prime. So 11 is an SG prime, and we have 1 confirmed as a possible SG units digit.

If p = 13, then 2p + 1 = 27, which is NOT prime. So 13 is NOT an SG prime.

Lets try 23:

If p = 23, then 2p + 1 = 47, which is also prime. So 23 is an SG prime, and we have 3 confirmed as a possible SG units digit.

Finally, lets check 9 as a units digit.

If p = 19, then 2p + 1 = 39, which is NOT prime. So 19 is NOT an SG prime.

But if p = 29, then 2p + 1 = 59, which IS prime. So 29 is an SG prime, and we have 9 confirmed as a possible SG units digit.

The product of 1, 3, and 9 is 27.

The correct answer is (D).

Special Announcement: If you want to win prizes for answering our Challenge Problems, try entering our Challenge Problem Showdown. Each week, we draw a winner from all the correct answers. The winner receives a number of our our Strategy Guides. The more people enter, the better the prize.