Even Integer N - Function Question

[chipbmk]

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!

[palvarez]

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