BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

Factorial & Prime

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Master | Next Rank: 500 Posts
Posts: 233
Joined: Wed Aug 22, 2007 3:51 pm
Location: New York
Thanked: 7 times
Followed by:2 members

Factorial & Prime

by yellowho » Sun Feb 27, 2011 11:08 pm
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.
Top
Source: — Problem Solving |
User avatar
GMAT Instructor
Posts: 905
Joined: Sun Sep 12, 2010 1:38 am
Thanked: 378 times
Followed by:123 members
GMAT Score:760

by Geva@EconomistGMAT » Sun Feb 27, 2011 11:22 pm
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.
Geva
Senior Instructor
Master GMAT
1-888-780-GMAT
https://www.mastergmat.com
Top
Master | Next Rank: 500 Posts
Posts: 233
Joined: Wed Aug 22, 2007 3:51 pm
Location: New York
Thanked: 7 times
Followed by:2 members

by yellowho » Sun Feb 27, 2011 11:25 pm
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]
Top
User avatar
GMAT Instructor
Posts: 905
Joined: Sun Sep 12, 2010 1:38 am
Thanked: 378 times
Followed by:123 members
GMAT Score:760

by Geva@EconomistGMAT » Sun Feb 27, 2011 11:37 pm
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.
Geva
Senior Instructor
Master GMAT
1-888-780-GMAT
https://www.mastergmat.com
Top
Master | Next Rank: 500 Posts
Posts: 233
Joined: Wed Aug 22, 2007 3:51 pm
Location: New York
Thanked: 7 times
Followed by:2 members

by yellowho » Sun Feb 27, 2011 11:48 pm
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!
Last edited by yellowho on Sun Feb 27, 2011 11:59 pm, edited 1 time in total.
Top
User avatar
GMAT Instructor
Posts: 905
Joined: Sun Sep 12, 2010 1:38 am
Thanked: 378 times
Followed by:123 members
GMAT Score:760

by Geva@EconomistGMAT » Sun Feb 27, 2011 11:56 pm
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.
Geva
Senior Instructor
Master GMAT
1-888-780-GMAT
https://www.mastergmat.com
Top
Post new topic Post Reply
• Page 1 of 1