Even Integer N - Function Question

[This topic has 1 member reply]
Forum Index GMAT Math Problem Solving
Free $100 Amazon.com Gift Card - Buy a GMAT course using a Beat The GMAT discount code between Mar 8-22 and get a $100 Amazon.com Gift Card. Learn more!
Post New Topic   Post Reply

chipbmk
Rising GMAT Star

Default Avatar

Joined: 05 Oct 2009
Posts: 70

Thanks given: 8
Thanked 0 times in 0 posts
Topic: Even Integer N - Function Question
PostTue Nov 17, 2009 11:05 pm
Elapsed Time:
00:00
 Lap   Why a timer is critical to improving your score
For every positive even integer n, the function h(n) is defined to be the product of all even integers from 2 to n inclusive. If p is the smallest prime factor of h(100) + 1, then p is between

a. 2 and 10
b. 10 and 20
c. 20 and 30
d. 30 and 40
e. > 40

OA: E

I think I have seen this one posted before, but I can't find it. Can someone please give me a clear explanation of how to solve this or link me to the original post?

Thanks!
Back to top
View user's profile Send private message
palvarez
Really wants to Beat The GMAT!

Default Avatar

Joined: 24 Oct 2009
Posts: 199

Thanks given: 3
Thanked 19 times in 17 posts

GMAT Score: 710
PostWed Nov 18, 2009 12:25 am
This is based on a famous theorem: "the number of primes is infinite". The proof goes along the following lines.

A = p_1*p_2*...*p_k +1, where p_i's are first k different prime numbers.

If A is a composite, A's prime factor can't be any of p_i and > p_k, which is the largest among first k primes.
If A is a prime, that prime can't any of p_i, and is greater than any p_i.

--------------------------------------------------------------------------------------------

h(100) + 1 = 2.4.6....100 +1 = 2^50 * 50! + 1

The above number is not divisible any any numbers from 2 to 50.

Assume that h(100)+1 is divided by k, such that 2 <=k <= 50

h(100) + 1 = 0 (mod) k

The right hand side = 1 (mod k)

reductio ad absurdum.


Therefore, if it has any prime factor, it must be greater than > 50

Answer: e
Back to top
View user's profile Send private message
Display posts from previous:   

Post New Topic   Post Reply All times are GMT - 7 Hours
Page 1 of 1
 
Forum Index GMAT Math Problem Solving
Most Active Members in Last 30 Days
1. harsh.champ 625 posts
2. shashank.ism 465 posts
3. ajith 370 posts
4. money9111 353 posts
5. thephoenix 349 posts
See More Top Beat The GMAT Members
Most Active Experts in Last 30 Days
1. lunarpower
Manhattan GMAT Teacher 		85 posts
2. Stuart Kovinsky
Kaplan GMAT Teacher 		70 posts
3. Lisa Anderson
Stacy Blackman Consulting 		50 posts
4. Testluv
Kaplan GMAT Teacher 		50 posts
5. Stacey Koprince
Manhattan GMAT Teacher 		35 posts
See More Top Beat The GMAT Experts