Author 
Message 
Manager
Joined: 07 Jan 2008
Posts: 87

For every positive even integer n, the function h(n) is [#permalink]
Show Tags
09 Feb 2008, 15:21
1
This post received KUDOS
This topic is locked. If you want to discuss this question please repost it in the respective forum.
For every positive even integer n, the function h(n) is defined to be the product of all the even integers from 2 to n, inclusive. If p is the smallest prime factor of h(100)+1, then p is between
A. between 2 and 10 B. between 10 and 20 C. between 20 and 30 D. between 30 and 40 E. greater than 40



CEO
Joined: 17 Nov 2007
Posts: 3584
Concentration: Entrepreneurship, Other
Schools: Chicago (Booth)  Class of 2011

Re: Prime numbers [#permalink]
Show Tags
09 Feb 2008, 15:28
Eh(100) contains all prime numbers between 2 and 47 inclusive. Obviously, these prime numbers cannot be factors of h(100)+1
_________________
HOT! GMAT TOOLKIT 2 (iOS) / GMAT TOOLKIT (Android)  The OFFICIAL GMAT CLUB PREP APP, a musthave app especially if you aim at 700+  PrepGame



Director
Joined: 31 Mar 2007
Posts: 576
Location: Canada eh

Re: Prime numbers [#permalink]
Show Tags
11 Feb 2008, 05:49
I got this one today. E.
Right answer, but I'm not sure either.
What rule is +1 makes it the next prime.... some sieve algorithm?



SVP
Joined: 28 Dec 2005
Posts: 1557

Re: Prime numbers [#permalink]
Show Tags
11 Feb 2008, 09:58
yeah, what is the fundamental rule and concept we are looking for here ?



Director
Joined: 01 Jan 2008
Posts: 622

Re: Prime numbers [#permalink]
Show Tags
11 Feb 2008, 10:19
pmenon wrote: yeah, what is the fundamental rule and concept we are looking for here ? n! + 1 doesn't have 2, 3, ... n as its factors. generalize m*(n!) + 1 doesn't have 2, 3, ... n as its factors. h(100) + 1 = 2^50*(50!)+ 1 doesn't have 2,3 ... 50 as its factors > E



Director
Joined: 31 Mar 2007
Posts: 576
Location: Canada eh

Re: Prime numbers [#permalink]
Show Tags
11 Feb 2008, 17:19
So basically you guys aren't using any theorem per say, but just doing some testing/playing around? That's what I did too, but I still don't understand why that works. Argh



CEO
Joined: 17 Nov 2007
Posts: 3584
Concentration: Entrepreneurship, Other
Schools: Chicago (Booth)  Class of 2011

Re: Prime numbers [#permalink]
Show Tags
11 Feb 2008, 23:41
StartupAddict wrote: So basically you guys aren't using any theorem per say, but just doing some testing/playing around? That's what I did too, but I still don't understand why that works. Argh only basic principles: 1. N=h(100) contains all prime numbers from 2 to 47. In other words, N is divisible by any prime number from set{2..47}. 2. M=h(100)+1. we can choose any prime number (p) from the set and write: M=p*s+1, where s is an integer. 3. M=p*s+1 means that M has reminder 1 for any prime numbers from the set. 4. Therefore, h(100)+1 is not divisible by prime number less or equal than 47. Hope this help.
_________________
HOT! GMAT TOOLKIT 2 (iOS) / GMAT TOOLKIT (Android)  The OFFICIAL GMAT CLUB PREP APP, a musthave app especially if you aim at 700+  PrepGame



SVP
Joined: 28 Dec 2005
Posts: 1557

Re: Prime numbers [#permalink]
Show Tags
12 Feb 2008, 18:47
walker wrote: StartupAddict wrote: So basically you guys aren't using any theorem per say, but just doing some testing/playing around? That's what I did too, but I still don't understand why that works. Argh only basic principles: 1. N=h(100) contains all prime numbers from 2 to 47. In other words, N is divisible by any prime number from set{2..47}. 2. M=h(100)+1. we can choose any prime number (p) from the set and write: M=p*s+1, where s is an integer. 3. M=p*s+1 means that M has reminder 1 for any prime numbers from the set. 4. Therefore, h(100)+1 is not divisible by prime number less or equal than 47. Hope this help. how does N=h(100) contain all prime numbers from 2 to 47 ? h(100) is product of all even numbers from 2 to 100 ... and 2 is the only even prime.



Director
Joined: 01 May 2007
Posts: 793

Re: Prime numbers [#permalink]
Show Tags
12 Feb 2008, 19:22
I got E as well...here is my thinking...
Unfortunately, I actually starting multiplying #s.
I made it 2 > 10 instead of 100
which came to 3840 + 1. Basically, we need to be able to have a prime divisor of 3840 and 1. The only divisor of 1 is 1, and that is not prime. Hence only 1 and 3841 can be a factor...I believe 3841 is prime. Unfortunately, I needed to actually start multiplying #s in order to see what we needed here.
Is my reasoning right?
Also...if this said h(100) + 2 would the answer for p be 2?



CEO
Joined: 17 Nov 2007
Posts: 3584
Concentration: Entrepreneurship, Other
Schools: Chicago (Booth)  Class of 2011

Re: Prime numbers [#permalink]
Show Tags
12 Feb 2008, 20:25
pmenon wrote: how does N=h(100) contain all prime numbers from 2 to 47 ? h(100) is product of all even numbers from 2 to 100 ... and 2 is the only even prime. N=h(100)=2*4*6*8....*98*100=2^50* 1*2*3*4*5....*47*48*49*50.
_________________
HOT! GMAT TOOLKIT 2 (iOS) / GMAT TOOLKIT (Android)  The OFFICIAL GMAT CLUB PREP APP, a musthave app especially if you aim at 700+  PrepGame



SVP
Joined: 28 Dec 2005
Posts: 1557

Re: Prime numbers [#permalink]
Show Tags
12 Feb 2008, 20:48
walker, can you dumb it down one more step for me please ?
N= h(100) = 2*4*6*8*...8*100 = 2*2^2*6*2^3 ...
where do you go from here ?



CEO
Joined: 17 Nov 2007
Posts: 3584
Concentration: Entrepreneurship, Other
Schools: Chicago (Booth)  Class of 2011

Re: Prime numbers [#permalink]
Show Tags
12 Feb 2008, 20:59
pmenon wrote: walker, can you dumb it down one more step for me please ?
N= h(100) = 2*4*6*8*...8*100 = 2*2^2*6*2^3 ...
where do you go from here ? h(100) = 2*4*6*8*10*12...96*98*100 h(100) = 2*(2*2)*(2*3)*(2*4)*(2*5)*(2*6)...(2*48)*(2*49)*(2*50) h(100) = 2^50*(2*3*4*5*6...48*49*50)
_________________
HOT! GMAT TOOLKIT 2 (iOS) / GMAT TOOLKIT (Android)  The OFFICIAL GMAT CLUB PREP APP, a musthave app especially if you aim at 700+  PrepGame



CEO
Joined: 17 Nov 2007
Posts: 3584
Concentration: Entrepreneurship, Other
Schools: Chicago (Booth)  Class of 2011

Re: Prime numbers [#permalink]
Show Tags
12 Feb 2008, 21:11
jimmyjamesdonkey wrote: I got E as well...here is my thinking...
Unfortunately, I actually starting multiplying #s.
I made it 2 > 10 instead of 100
which came to 3840 + 1. Basically, we need to be able to have a prime divisor of 3840 and 1. The only divisor of 1 is 1, and that is not prime. Hence only 1 and 3841 can be a factor...I believe 3841 is prime. Unfortunately, I needed to actually start multiplying #s in order to see what we needed here.
Is my reasoning right?
I guess it is an incorrect way. You are simply lucky with your answer if you prove that h(10)+1 is a prime number, you cannot say that h(12)+1 is also a prime number. By the way, 3841 is not a prime number: 3841=23*167. jimmyjamesdonkey wrote: Also...if this said h(100) + 2 would the answer for p be 2? Agree.
_________________
HOT! GMAT TOOLKIT 2 (iOS) / GMAT TOOLKIT (Android)  The OFFICIAL GMAT CLUB PREP APP, a musthave app especially if you aim at 700+  PrepGame



Director
Joined: 20 Aug 2007
Posts: 851
Location: Chicago
Schools: Chicago Booth 2011

Re: Prime numbers [#permalink]
Show Tags
13 Feb 2008, 07:37
walker wrote: pmenon wrote: walker, can you dumb it down one more step for me please ?
N= h(100) = 2*4*6*8*...8*100 = 2*2^2*6*2^3 ...
where do you go from here ? h(100) = 2*4*6*8*10*12...96*98*100 h(100) = 2*(2*2)*(2*3)*(2*4)*(2*5)*(2*6)...(2*48)*(2*49)*(2*50) h(100) = 2^50*(2*3*4*5*6...48*49*50) That's some incredible number properties skills there. nice job.










