yellowho wrote:For any integer p greater than 1, &p& denotes the product of
all the integers from 1 to p, inclusive. How many prime
numbers are there between &5& and &5& +7, inclusive?

How do you do this without multiplying out?


The only way I can think of is factor out 5!+1,5!+2, 5!+3,etc..... all the way to 5!+6 and 5!+7. Then you have to multiply and test.

You dont need to actually factor each number: all you care about is whether the sum of 5!+integer is divisible by another integer or not: If it's divisible by another number, it's not prime.
The principle tested here is that result of adding multiples of the same number. Multiple of x + multiple of x must also result with a multiple of x, since you can extract x as a common factor.

For example, 5!+2 is divisible by 2, since 5! is also a multiple of 2: 5! is equal to 5*4*3*2*1, so it is possible to extract 2 as a common factor:
5!+2 = 2(5*4*3*1 +1)

So by the same rationale, 5!+any integer up to 5 will not be prime, since 5! itself is also divisible by the integers up to 5, resulting with a sum of two multiples of x.
The same could be said about 6: 5!+6 is divisible by 3 and 2, since both 5! and 6 are multiples of 3 and 2. So 5!+6 is not prime.
The only prime here is 5!+7 - there's no common factor (other than 1) you can extract from this both 5! and 7, so the sum is not divisible by any integer other than 1 and itself.

Answer is 1 - there's only 1 prime from the 7 integers described.

Thanks Geva! Can you elaborate on the last point a little more [b]"there's no common factor (other than 1) you can extract from this both 5! and 7, so the sum is not divisible by any integer other than 1 and itself. "[/b]


I still don't quite see the logic there yet.




[quote="Geva@MasterGMAT"][quote="yellowho"]For any integer p greater than 1, &p& denotes the product of
all the integers from 1 to p, inclusive. How many prime
numbers are there between &5& and &5& +7, inclusive?

How do you do this without multiplying out?


The only way I can think of is factor out 5!+1,5!+2, 5!+3,etc..... all the way to 5!+6 and 5!+7. Then you have to multiply and test.[/quote]

You dont need to actually factor each number: all you care about is whether the sum of 5!+integer is divisible by another integer or not: If it's divisible by another number, it's not prime.
The principle tested here is that result of adding multiples of the same number. Multiple of x + multiple of x must also result with a multiple of x, since you can extract x as a common factor.

For example, 5!+2 is divisible by 2, since 5! is also a multiple of 2: 5! is equal to 5*4*3*2*1, so it is possible to extract 2 as a common factor:
5!+2 = 2(5*4*3*1 +1)

So by the same rationale, 5!+any integer up to 5 will not be prime, since 5! itself is also divisible by the integers up to 5, resulting with a sum of two multiples of x.
The same could be said about 6: 5!+6 is divisible by 3 and 2, since both 5! and 6 are multiples of 3 and 2. So 5!+6 is not prime.
The only prime here is 5!+7 - there's no common factor (other than 1) you can extract from this both 5! and 7, so the sum is not divisible by any integer other than 1 and itself.

Answer is 1 - there's only 1 prime from the 7 integers described.[/quote]

yellowho wrote:Thanks Geva! Can you elaborate on the last point a little more "there's no common factor (other than 1) you can extract from this both 5! and 7, so the sum is not divisible by any integer other than 1 and itself. "


I still don't quite see the logic there yet.

Ok, let's spell it out a bit:

5!+1 is not prime: it's 5*4*3*2*1 + 1 = 121, which is 11^2. this is an anomaly that needs to be tested specifically: the rest are sums of two integers with a common factor, and that factor can be extracted as a common factor, so the sum is divisible by another number:

5!+2 is not prime, since 5*4*3*2*1 + 2 can be written as 2(5*4*3*1 + 1) = 2*some big integer, so the sum is divisible by at least 2.
5!+3 is not prime, since 5*4*3*2*1 + 3 can be written as 3(5*4*2*1 + 1) = 3*some big integer, so the sum is divisible by at least 3.

etc.

The same goes for 4, 5 and 6: in all of these cases, the 5! and the added integer share some common factor that can be extracted, so the sum is divisible by at least that number.

The same CANNOT be said of 5!+7 = 5*4*3*2*1 and 7 do not share any common factor, so it is impossible to extract a common factor to make sure that the sum is divisible by that common factor.

With all the other terms we are able to prove they are not prime because we are able to prove they are divisible by numbers other than itself. With 5!+7, we can't prove that its not divisible by a number other than itself readily. Does that automatically mean it's prime? Or should we test them? With 5!+7 we just know its not divisible by (2)^3*(3)*(5) or any of its factors and of course 7 right?




The logic I actually used here to skip testing is Multiple+non-multiple = Non-multiple. Just wanted to make sure that is right. I think that's what you were referring to.

THanks!

yellowho wrote:With all the other terms we are able to prove they are not prime because we are able to prove they are divisible by numbers other than itself. With 5!+7, we can't prove that its not divisible by a number other than itself readily. Does that automatically mean it's prime? Or should we test them?

The logic I actually used here to skip testing is Multiple+non-multiple = Non-multiple. Just wanted to make sure that is right. I think that's what you were referring to.

THanks!

Indeed.