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

Redeem

Even Integer N - Function Question

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Senior | Next Rank: 100 Posts
Posts: 70
Joined: Mon Oct 05, 2009 9:33 am

Even Integer N - Function Question

by chipbmk » Tue Nov 17, 2009 10:05 pm
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!
Top
Source: — Problem Solving |
Master | Next Rank: 500 Posts
Posts: 199
Joined: Sat Oct 24, 2009 4:43 pm
Thanked: 22 times
GMAT Score:710

by palvarez » Tue Nov 17, 2009 11:25 pm
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
Top
Post new topic Post Reply
• Page 1 of 1