Problem Solving

steinbock wrote:Got this wrong on my prep test. Can someone help?

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

A) Between 2 and 10
B) Between 10 and 20
C) Between 20 and 30
D) Between 30 and 40
E) Greater than 40

OA is E

The explanation in the previous post is incorrect.

Notice that h(100) = 2*4*6*...*98*100
so h(100) = 2^50 * 50!

The point here is that h(100) is divisible by everything up to 50-- it's equal to 2^50 * 50!, and 50! is divisible by everything less than or equal to 50.

So, you can divide h(100) by any prime less than 50. That guarantees that h(100) + 1 will *not* be divisible by any prime less than 50. Try dividing it by, say, 37: h(100) is divisible by 37, so you'll get a remainder of 1 when you divide h(100) + 1 by 37, since h(100)+1 is one greater than a multiple of 37. Because of this, there's no way you can divide h(100)+1 by any prime less than 50- every time the remainder is certain to be 1.

So, what's the smallest prime divisor of h(100) + 1? That would take a very long time to work out, believe me. But we can be sure it's greater than 50.