Prime Time

(This is one of a series of GMAT tips that we offer on our blog.)

A recent episode of “The Office” featured a classic, GMAT-relevant exchange, in which a cash-strapped Michael Scott asks his financial analyst to “crunch those numbers again”. The stunned analyst explains that, because the calculations were all done accurately using a computer program, there was no mechanism for “crunching” the numbers again, and even if there were, there would be no change.

Such is life in business nowadays. Sophisticated machines do a lot of the “number crunching” for us, and business managers are much more often in the business of analyzing numbers than of crunching them. The GMAT, in an attempt to determine the candidates best suited to thrive in such an environment, heavily features the analysis of numbers in similar ways, requiring you to think often about the properties of numbers.

A prime example of this is the examination of prime numbers on the GMAT. Prime numbers are those that have exactly two factors (itself and 1) – a seemingly simple definition that can often become cumbersome to employ on the GMAT. One such way in which prime numbers can lead to frustration is a question like the following:

How many prime numbers are between 110 and 120?

It’s unlikely that you’ll have memorized the list of prime numbers up in to the triple-digits, so you will probably approach this question by taking the set of numbers and eliminating any numbers that are not prime. Even numbers, by definition, are divisible by 2, so the even numbers in this set are definitely not prime, leaving us with a set of:

111

113

115

117

119

It’s also relatively easy to eliminate 115, because a number ending in 5 is divisible by 5, so we’re down to four numbers remaining. 111 and 117 are each divisible by 3 (there’s a trick for making that determination that we’ll probably feature in an upcoming GMAT Tip of the Week), so we’re left to test:

113

119

This is where it may get tricky, as in order to prove that a number is prime, we need to prove that it is not divisible by anything but itself and 1. With a 3-digit number, this process could be time consuming without these two principles:

1) You don’t need to test for divisibility by anything other than prime numbers.

If a number is divisible by, say, 4, it needs to also be divisible by 2, because 4 is divisible by 2. So, if you’ve already determined that 113 is not divisible by 2, you don’t need to test to see if it is divisible by 4 (or 6, or 8, etc.).

2) You don’t need to test a number by anything higher than the square root of the next-highest perfect square.

This is probably best illustrated by an example. With 113, the next highest square above it is 121, and we know that 121 is the same as 11*11. So, logically speaking, in order for a number greater than 11 to multiply with another integer to produce a number smaller than 121, that other integer must be less than 11. If it were greater than 11, the product would be higher than 121.

If we test 113 by the other primes (7 and 11), we find that it’s not divisible by 7 (7*10 = 70 and 7*6 = 42, so 7*16 is 112, meaning that 113 cannot be divisible by 7… but also that 119 is divisible by 7. So, our work with 119 is done.).

It’s also not divisible by 11 (11 * 10 = 110, so we know that 113 is not a multiple of 11).

Now, because we’ve already tested everything up to 11, we’re done…we know that 113 is prime. Again, if 113 were to be divisible by 13, it would also have to be divisible by something less than 11, because we know that 11*11 is already too high. So, there’s no need to test 113 for divisibility by anything other than what we already have, and we can prove that the answer to the overall question is 1.

If you’re getting ready to take the big test soon, try our free practice GMAT. And, as always, be sure to follow us on Twitter!