ricaototti wrote:In a sequence of 13 consecutive integers, all of which are less than 100, there are exactly 3 multiples of 6. How many integers in the sequence are prime?

1) Both the multiples of 5 in the sequence are also multiples of either 2 or 3.
2) Only one of the two multiples of 7 in the sequence is also not a multiple of 2 or 3

I assume the question intends for the 13 consecutive integers to all be positive- otherwise the answer is clearly E. Even if we assume this, as written, the answer is E anyway; using both statements, the sequence could be 6, 7, ..., 18, which contains four primes (7, 11, 13, 17), or it could be 42, 43, ..., 54, which contains three primes (43, 47, 53).

I'd like to add one further restriction to the question, that the integers are all larger than 10, which makes the question more interesting. This rules out the example of 6, 7, ..., 17, 18 used above, and guarantees that if a number in our list is divisible by 7, it isn't prime. We'll use that later. Assuming this:

First, if a number is greater than 1 and less than 100, it is either prime, or it is divisible by at least one of 2, 3, 5 or 7 (because every positive integer x larger than 1 that is not prime has a prime factor less than or equal to sqrt(x)).

We can write our sequence as follows: 6k, 6k+1, 6k+2, ..., 6k + 11, 6k + 12. Seven of these numbers must be even, and 6k+3 and 6k+9 are both divisible by 3. The only possible primes are:

6k+1
6k+5
6k+7
6k+11

From 1, we know that none of these four numbers is a multiple of 5; all the multiples of 5 in the list are divisible by 2 or 3, so we have already ruled them out. Still, one of them might be divisible by 7.

From 2, we know that exactly one of these numbers is a multiple of 7, and therefore one of the four numbers in the list above is certainly not prime (this is where I'm using the assumption that all the integers are greater than 10). We don't know whether any are multiples of 5, however.

Since from 1 and 2 together we know that exactly three of the numbers in the list above are not divisible by 2, 3, 5 or 7, the statements together must be sufficient. There are three primes. C.

One can still find examples to demonstrate that neither statement is sufficient on its own; for 1), the set could be 12, ..., 24, which contains four primes, or 42, ..., 54, which contains three primes. For 2), the set could be 48, ... 60 which contains only two primes, or 42, ..., 54 which contains three primes.

ricaototti wrote:Ian, thanks a lot! You are a genius. Great explanation.

But how can we be sure that none of the elements left is a multiple of other primes like 11?

That is a very good question, that I addressed, perhaps too briefly, above when I wrote:

every positive integer x larger than 1 that is not prime has a prime factor less than or equal to sqrt(x)

We can look at this in another way: if a number x is *not* prime, is *not* divisible by 2, 3, 5 or 7, but *is* divisible by 11, what is the smallest possible value of x? Well, we know x is divisible by 11, so x = 11k, for some value of k which is not divisible by 2, 3, 5 or 7. The smallest possible value of k is thus the smallest prime greater than 7, which is 11, and the smallest possible value of x is 11^2 = 121. This proves that every multiple of 11 which is greater than 11 and smaller than 121 is also divisible by another prime- 2, 3, 5 or 7.

This is how we test whether a number is prime (although this is very time consuming for large numbers):

If a number x has any divisor at all besides 1 and x, it must:

-have a prime divisor
-have a prime divisor which is pretty small: it must have a prime divisor less than sqrt(x)

So if you want to know if x is prime, you can:

-estimate, very quickly, sqrt(x), by finding the nearest perfect square to x
-write down all the primes less than sqrt(x)
-test if x is divisible by any of these primes. If not, x is prime.

You can use this to answer a question like the following:

How many primes are there between 140 and 150?

* Each of these numbers is less than 13^2 = 169, so the square root of each is less than 13.

* The primes less than 13 are 2, 3, 5, 7 and 11.

* We now only need to check whether the numbers between 140 and 150 are divisible by these primes. Rule out the even numbers, the odd multiples of 3 (sum the digits: 141 and 147) and the odd multiple of 5 (145), which leaves us with only two candidates: 143 and 149. Neither can be divided by 7, but 143 is divisible by 11 (143 = 11*13).

* Since 149 cannot be divided by any prime less than sqrt(149), 149 must be prime.

So there is only one prime between 140 and 150.

Finally, I'd add that this is only occasionally tested on the GMAT, and there are much more important things to know in Number Theory- in particular, it is much more helpful to understand the importance of prime factorizations, and the concept of a remainder.